The Church-Turing Thesis (Hello World tester) contradiction and randomized algorithms

Question

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

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.

Answer 1

The Church-Turing thesis proves that there is no algorithm (or program) 𝐻 that says whether a program 𝑃 written in a language, say 𝐶, on an input 𝐼 outputs the sentence Hello World or not. This is his proof, visit Hopcraft and etc.

The Church-Turing thesis is introduced in the book as "the unprovable assumption that any general way to compute will allow us to compute only the partial-recursive functions (or equivalently, what Turing machines or modern-day computers can compute)". It has little to do with undecidability directly. I will treat "The Church-Turing thesis proves that" as a typo that should not exist.

---

Please explain where I am wrong about this.

In fact, you are not necessarily wrong at all. It is just that your argument does not lead us anywhere.

What have been proved in the book is that there is no non-randomized algorithm that can decide whether a non-randomized program on an input outputs "Hello World" or not. No, there is no such adjective "non-randomized" in the original statement in the book. However, it does not matter much whether we add it or not. Why?

Because a randomized algorithm cannot decide anyway. It can only say something like the probability a given program on some given input outputs "Hello world" is less than 23 percent. I will not call that probabilistic prediction a decision. You have not found anything valuable or interesting by considering randomized algorithms. All you have observed is that the proof does not apply to randomized algorithms, which we do not have to consider in the first place anyway.

---

We might be thinking, wait, there is some information if we can be certain the probability a given program on some given input outputs "Hello world" is less than 23 percent. That could be mean that the undecidability only holds in some relative sense.

However, the conclusion is still something along the line that there is no algorithm, whether randomized or not, can always provide non-zero information regarding whether a deterministic program on a input outputs "Hello world" or not. You can read the question can a probabilistic Turing machine solve the halting problem? and its answers for more explanations.