-3
$\begingroup$

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

That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not halt), then why is it meaningful for it to be called "Turing complete"? Wouldn't it make sense that "Turing complete" is also such that it avoids e.g the halting problem?

This could be seen to be more harmonious with the concept of completeness such as when contrasted to e.g. completeness of Banach:

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

Since infinite computation does not converge, then in this contrast it doesn't feel like "complete".

$\endgroup$
  • $\begingroup$ What do you mean by "expresses infinite computation" and "avoids the halting problem"? $\endgroup$ – David Richerby Jan 18 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 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$ – David Richerby Jan 19 at 0:46
  • $\begingroup$ ... the problem of adding numbers" makes no sense. And, again, what do you mean by "expresses infinite computation"? $\endgroup$ – David Richerby Jan 19 at 0:46
6
$\begingroup$

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, we have decision problems. A decision problem can be given by defining a set of strings; the problem is to decide, given a string, whether it is a member of the set.

Given a set of strings, we can define its characteristic function as the function that maps every member of the set to "Y" and every non-member to "N".

A set is decidable if its characteristic function is computable: some Turing machine decides membership of the set for arbitrary strings. A set is undecidable if no such Turing machine exists. Undecidable sets exist.

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. No violation is going on here.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Good, but do you answer how undecidability relates to Turing completeness? Or does Turing completeness include also infinite computation? $\endgroup$ – mavavilj Jan 17 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 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 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 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 at 20:27
1
$\begingroup$

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.

$\endgroup$

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