patternMinor
Do all Turing-complete programming languages have to contain infinite loops?
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:
How could this be proven (or disproven)?
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$:
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.
- 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.