The Church-Turing thesis proves that there is no algorithm (or program) $H$ that says whether a program $P$ written in a language, say $C$, on an input $I$ outputs the sentence
Hello World or not. This is his proof, visit Hopcraft and etc.
introduction to automata theory languages and computation, chapter 8.
The prove is by contradiction. Let there is such a program $H$ to do the task. He made several simple changes to $H$ and built a program $H_2$, then showed $H_2$ doesn't exits.
The program $H$ is as follows
On input $P$ and $I$, it outputs
no which tells if the output is
Hello World or not.
He then build program $H_1$ as follows
$H_1$ takes $P$ and $I$ and runs $H$ on $P$ and $I$, if $H$ prints
yes, it prints
yes and if $H$ prints
no, it prints
Hello World. The $H_1$ is as follows
He then built $H_2$ as follows
- $H_2$ reads the $P$ and store in an array $A$.
- $H_2$ simulates the $H_1$, but whenever $H_1$ would read an input, $H_2$ reads from stored copy in $A$.
Hence $H_2$ prints
yes if $P$ prints
Hello World when given itself as input and
Hello world if doesn't print
The contradiction occurs when when the $P$ is actually program $H_2$, the source code of $H_2$ is provided as input to itself. If the $H_2$ prints
Yes, then $H_2$ in the box saying $H_2$ on input $H_2$ prints
Hello World and the
Hello World is the output of
no in $H$.
The basis of contradiction is, $H_2$ on input source code of $H_2$ printed
nowhile we assumed it is
yesand a program on the same input can't have different outputs.
If $H$ were a program with randomized algorithm, then on the same input it would have different outputs. The basis of the contradiction is if $H_2$ on input $H_2$ prints something, it can't print something else on $H_2$ again. But if $H$ contains some random process inside it, then on the same input it would print different things and it is not a contradiction at all.
Please explain where I am wring about this.
Thanks in advance.