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 yes
or 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 Hello World
.
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
no
while we assumed it isyes
and 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.