6
$\begingroup$

Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below:

Conjecture. There does not exist a set $S$ of Turing machines such that all three of these properties hold:

  • $S$ is decidable. (That is, there exists a Turing machine that checks whether a Turing machine description is in $S$.)
  • $S$ is Turing-complete. (That is, for every decidable language $L$, there exists some Turing machine in $S$ that decides $L$.)
  • All Turing machines in $S$ halt on all input strings.

How could this be proven (or disproven)?

$\endgroup$
1

2 Answers 2

5
$\begingroup$

Suppose that such a set $S$ existed. Consider the following program, which accepts an input $x$:

  • Check whether $x \in S$. If not, return TRUE.
  • Run $x$ on $x$, and return the opposite.

By assumption, the corresponding language $L$ is decidable, and so there exists some $x \in S$ that decides it. We get a contradiction by considering whether $x \in L$ or not.

$\endgroup$
5
  • 2
    $\begingroup$ Such an elegant proof! Given this answer, I realized the conjecture is a direct application of Rice's theorem: A set $S$ that satisfies the last two properties is a nontrivial subset of all Turing machines, hence undecidable. $\endgroup$
    – John L.
    Mar 31, 2022 at 18:02
  • $\begingroup$ @JohnL. This does not follow from Rice’s theorem, since membership of this set $S$ might not be a semantic property. $\endgroup$ Apr 1, 2022 at 7:37
  • $\begingroup$ @TheemathasChirananthavat As long as Yuval does not object, I am confident I am right. :) $\endgroup$
    – John L.
    Apr 1, 2022 at 7:43
  • $\begingroup$ Does this proof use the “always halts” condition anywhere? $\endgroup$ Apr 1, 2022 at 7:47
  • 2
    $\begingroup$ This guarantees that the language is decidable, since the machine I consider always halts. $\endgroup$ Apr 1, 2022 at 8:05
0
$\begingroup$

I think there might be two questions in this.

  1. Do all Turing complete programming languages have to contain infinite loops? Yes. Turing complete <=> Simulate any Turing machines. As there are Turing machines with infinite loops your statement has to be true.

  2. How to (dis)prove your Conjuncture. One has to either find a Set S that has these properties to prove it OR find that one property can not be achieved while any of the other two are achieved.

I only have a non conclusive proof for this: An Emulator on a normal PC needs to run forever (Turing completeness ignores pesky physics), not for a million years but forever (theoretically). The PC running this program would be a Universal Turing machine. As previously stated Turing complete <=> Simulate any Turing machines. Your Set would need to be able to simulate this UTM which sometimes does not halt. Meaning your Set can be only Turing complete or halt on all Inputs but not both

$\endgroup$
1
  • 1
    $\begingroup$ You don't necessarily need to run a Turing machine in order to simulate it. The notion of simulation only demands that the end result be the same. It doesn't care how this is achieved. $\endgroup$ Mar 31, 2022 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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