The whole program as a unit, as start variable "S" in DCFG grammar and  Rice Theorem.
Channel: Somenath Roy Choudhury
Date: 13/05/2022

In 1936, Turing published his paper "On Computable Numbers, with an Application to the Entscheidungsproblem". 

In this paper, Turing reformulated Kurt Gödel's 1931 results on the limits of proof and computation, replacing Gödel's universal arithmetic-based formal language with the formal and simple hypothetical devices that became known as Turing machines. 

The Entscheidungsproblem (decision problem) was originally posed by German mathematician David Hilbert in 1928. Turing proved that his "universal computing machine" would be capable of performing any conceivable mathematical computation if it were representable as an algorithm. He went on to prove that there was no solution to the decision problem by first showing that the halting problem for Turing machines is undecidable: it is not possible to decide algorithmically whether a Turing machine will ever halt. This paper has been called "easily the most influential math paper in history".

RICE theorem( year1951)  can elaborate Turing Halting problem.

Henry Gordon Rice (July 18, 1920 – April 14, 2003) was a logician and mathematician best known as the author of Rice's theorem (1953), which he proved in his doctoral dissertation of 1951 at Syracuse University.

How Languages can be Represented
• A language is a set of strings.
• A language can be finite or infinite.
• In general, there is no way to “write down” all elements of a language for conveyance.
• So we need some other representation as a means of conveyance.

How Languages can be Represented
One representation as a means of conveyance:
o Our focus is on languages that are recognizable by Turing machines.
o In other words, a Turing machine represents the language.
o The whole language is represented by a single finite string.
Rice’s Theorem, Informally
• Practically no functional properties (to be defined) of recognizable languages are decidable.
• The caveat here is that the theorem only applies to functional properties, not structural ones.
• The concept of structural vs. functional is used in software testing (white-box vs. black-box testing).
Property = Language Membership
A TM's language having a property is just another way of saying its code is in the language of all TM codes having that property.

Example properties of a language:
o All strings in the language are even-length.
o The language consists of descriptions of TM's that always halt.
o The language is infinite.
o The language is empty.