The Church-Turing Thesis (Hello World tester) contradiction and randomized algorithms
The <PERSON>-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. 603
The $H_1$ is as follows
He then built $H_2$ as follows
1. $H_2$ reads the $P$ and store in an array $A$.
2. $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 is yes 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. 610