0
$\begingroup$

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

Hello World tester-Church Turing thesis

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

Hello World tester-Church Turing thesis

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$.

Hello World tester-Church Turing thesis

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you very much for your useful answer. I still can design a non-randomized program to produce different outputs on the same input. For example the program may consider the current time of the system, if its second is odd, print yes, otherwise no. This is non-randomized and the proof is not applicable to this kind of algorithms. What do you think about this? $\endgroup$ – M a m a D Feb 2 '19 at 11:48
  • $\begingroup$ How is the current time used, assuming it is not part of the input? If the output does not depend on it, then the program is equivalent to a deterministic program to which the proof is applicable. If the output of the program does depend on the current time, then it is not reasonable to consider it as a program/algorithm in the first place. "In the case of random output, it is no longer formally effective", says Wikipedia. $\endgroup$ – John L. Feb 5 '19 at 15:27
  • $\begingroup$ Note that not all "programs" as spoken loosely are programs/algorithms in the usual sense as defined/explained in the textbooks for computer science. A simple usage of the current time by a process may make it inappropriate to call that process an algorithm. $\endgroup$ – John L. Feb 5 '19 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.