Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"?

The halting problem:

The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation


The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input.

Now, if one has a language that's Turing complete, but expresses a program of infinite computation (i.e. may not halt), then why is it meaningful for it to be called "Turing complete"?

Contrast this to the notion of completeness in Banach spaces:

a real normed vector space $V$ is called complete if every Cauchy sequence in converges in $V$.

So if the notion on "completeness" would be similar to this, it would have to mean that Turing complete programs "always converge"?

Or perhaps the usages of "completeness" are not similar here?

That is, as I've read. Turing-completeness includes infinite computations, infinite memory and such. Thus is expresses "completeness" in "wholeness" sense, rather than as "convergence" sense?

  • $\begingroup$ What do you mean by "expresses infinite computation" and "avoids the halting problem"? $\endgroup$ Jan 18 '19 at 15:57
  • $\begingroup$ @DavidRicherby Halting problem: TM doesn't know what to do and therefore runs forever. Avoids the halting problem: TM always knows how to halt (e.g. infinite computations would be solved somehow). $\endgroup$
    – mavavilj
    Jan 18 '19 at 17:38
  • $\begingroup$ Sorry but that's not what the halting problem is. The halting problem is not a problem in the sense of "A problem in the world today is terrorism" (as in, a bad thing that we somehow have to deal with); it's a problem in the sense of "My teacher set us three problems for homework" (i.e., a task that we wish to solve). The halting problem is: you are given a computer program and an input for that program, and you must determine whether or not that program halts when run with that input. So, again, what do you mean by "avoids the halting problem". That doesn't make sense, just like "avoids... $\endgroup$ Jan 19 '19 at 0:46
  • $\begingroup$ ... the problem of adding numbers" makes no sense. And, again, what do you mean by "expresses infinite computation"? $\endgroup$ Jan 19 '19 at 0:46

You do not yet understand what Turing completeness means.

Turing completeness is the ability to perform arbitrary finite computations.

To simplify matters, we say an arbitrary finite computation is an effective procedure that, given some (finite) input, produces some (finite) output, after some (finite number of) steps. To simplify matters further, we assume the output for a given input is the same every time.

That is to say: the effect of a computation is a function from strings (finite sequences of symbols) to strings.

(Not all computations in practice are of this type, but as far as computability is concerned, they can be shown to correspond to a computation of this type.)

So the inputs, the outputs, and the numbers of steps are all finite. However, the set of possible inputs and the set of possible outputs can be infinite.

Such a function is called computable if and only if some Turing machine computes it. That is to say, the Turing machine, when started on a tape containing an input to the function, will always terminate with a tape containing the output defined by the function for that input.

It turns out that not all functions from strings to strings are computable.

In particular, not all functions from strings to {"Y", "N"} are computable. These functions effectively say whether a string is a member of a certain set (the function says "Y" if it is, and "N" if it is not).

A set is decidable if some Turing machine computes its "Y"/"N" function. Not all sets are decidable.

A programming language is Turing complete if it can compute all functions that a Turing machine can compute. Amongst other things, this means it can decide any decidable set. Undecidable sets are the ones that no Turing machine can decide. No programming language can decide those sets (says the Church-Turing thesis; I could substantiate this, but this answer is too long already), not even when it is Turing complete.

In short: Turing completeness means a programming language can do everything a Turing machine can do. It doesn't mean it can do things a Turing machine cannot do, such as deciding undecidable sets. No violation is going on here.


"Turing complete" is defined as "able to do everything a Turing machine can do, if you give it enough resources". All modern programming languages are either Turing complete or "effectively" (*) Turing complete, simply because it's hard to be a useful programming language without that.

In particular, if you have…

  • Some basic means of doing arithmetic, like an "increment" instruction
  • Some basic means of storing variables
  • Some way of checking the value of a variable, and branching based on it
  • Some way to make a loop (i.e. branch/jump backward)

…then your language is most likely Turing-complete. It's been shown that the language SUBLEQ, in which the only instruction is "subtract $a$ from $b$, then branch to $c$ if $d \leq 0$", is Turing-complete. Same with the language Brainfuck, which is about as simple as you can possibly go.

For some other examples, it's been shown that Magic: the Gathering is Turing-complete. Same with Pokémon Yellow, the Sendmail configuration file, Internet routers, and PowerPoint presentations.

And Turing proved that for anything Turing-complete, there are certain problems that can never be solved. The Halting Problem is one of these. That means that, for example, it's possible to get into a situation in a Magic: the Gathering game where whether or not the game ever ends is undecidable, or to create a Sendmail configuration that can't be proven to ever finish starting up.

In other words, it's really hard to make something that's useful for computation but not Turing complete.

So, what's so special about Turing completeness? It sounds like a pretty weak property, if things like Sendmail config files have it.

The key is…nobody's ever found something stronger than Turing completeness. That is, nobody's ever been able to make an algorithm that X fancy new machine can run, but a Turing machine can't. In theory, anything your computer can do, a game of Magic: the Gathering can do. Or a PowerPoint presentation, or Conway's Game of Life. Some people claim that human consciousness can do things a Turing machine can't, but even that is questionable: look into the Church-Turing Thesis.

TL;DR: Turing completeness is useful because weaker models aren't very interesting (**), and stronger models have never been proven to exist.

(*) C, for example, isn't technically Turing complete, because of some lawyerly details in the specification; what it comes down to is, adding more addressable memory makes it a different "implementation", which doesn't count as "the same" language. If you don't care about the fine print, and are happy to call "C with 32-bit pointers" and "C with 64-bit pointers" the same language, then it's Turing-complete.

(**) Well, this isn't quite true. Finite state automata, pushdown automata, and the like are all very interesting and useful for certain tasks. But they're also very limited, since it's been proven that they can never possibly do certain things that we want to do. For example, a finite state or pushdown automaton can never answer the question "are there the same number of As, Bs, and Cs in this string?"

  • $\begingroup$ Good, but do you answer how undecidability relates to Turing completeness? Or does Turing completeness include also infinite computation? $\endgroup$
    – mavavilj
    Jan 17 '19 at 19:33
  • $\begingroup$ @mavavilj Turing-complete means you can't determine by any means whether it'll halt. Added a bit; how's this? $\endgroup$
    – Draconis
    Jan 17 '19 at 19:40
  • $\begingroup$ Some sources I read didn't say that Turing complete requires decidability. Turing completeness is merely that the language is able to express any other language/machine (incl. those with infinite computation). So that Turing recognizability, decidability and completeness are somewhat related, but not equivalent criteria. $\endgroup$
    – mavavilj
    Jan 17 '19 at 20:02
  • $\begingroup$ I would agree on though that including "solves Halting problem" to Turing completeness would make "completeness" more reasonable. Since infinite computations are practically useless. $\endgroup$
    – mavavilj
    Jan 17 '19 at 20:04
  • $\begingroup$ @mavavilj The problem is, nobody's ever created a system that's (1) at least as strong as a Turing machine and (2) can solve the Halting Problem. It might be more useful, but nobody's ever been able to make one! $\endgroup$
    – Draconis
    Jan 17 '19 at 20:27

Turing completeness is a property of computational machinery/model (e.g. a programming language).

Undecidability is a property of a decision problem (e.g. set membership).

You may not, for some reason, like the usage of word “complete”, but both of the terms we are talking about have clear definitions that don’t rely on each other.
You could think of it as “undecidability” residing in the world above “Turing completeness”, it is a property on input sets to computational models.

Look up the proof for undecidability of the Halting problem and it should be clear that undecidability is inevitable, so there is no such thing as “avoiding Halting problem” with Turing complete models and stronger model has not been invented, probably never will.


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