HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Do all Turing-complete programming languages have to contain infinite loops?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infinitealllanguagescontainprogrammingloopscompleteturinghave

Problem

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)?

Solution

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.

Context

StackExchange Computer Science Q#150250, answer score: 5

Revisions (0)

No revisions yet.