1
$\begingroup$

I want to relate Turing completeness to the Halting Problem.

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But since Halting Problem can't be solved by any programming language so every programming language should be Turing Incomplete. Right?

But every where in internet it's written that modern programming languages like c++ are Turing Complete. Are they wrong or Did I Misunderstood something?

$\endgroup$
3
  • 4
    $\begingroup$ A machine is not turing complete if it can solve the halting problem, in fact it shows that turning machines can not solve the halting problem. $\endgroup$ Aug 19, 2023 at 8:24
  • 1
    $\begingroup$ Why do you think the halting problem can be solved in every programing language? It's trivial to solve create a program in any language such that if it halts is unknown (eg. the colatz conjecture) $\endgroup$
    – mousetail
    Aug 19, 2023 at 13:26
  • 4
    $\begingroup$ That's not Turing completeness. Turing completeness is any machine that can emulate a Universal Turing Machine. With the exception of having infinite memory (a theoretical Universal Turing Machine has infinite memory) all general purpose CPUs ever designed, built and sold can emulate a Universal Turing Machine - they're all Turing Complete. The computer you wrote this question on is definitely Turing Complete (minus having infinite memory) $\endgroup$
    – slebetman
    Aug 19, 2023 at 14:59

4 Answers 4

33
$\begingroup$

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task.

No. A model of computation is Turing-complete if it can compute any Turing-computable function (i.e., any computable function that can be computed by a Turing Machine).

An alternative, but exactly equivalent way to phrase it, is that a model of computation is Turing-complete if it can simulate any Turing Machine.

Another equivalent way is that a model of computation is Turing-complete if it can simulate a Universal Turing Machine (which is just a Turing Machine which can simulate any other Turing Machine).

Yet another way to phrase it is that a model of computation is Turing-complete if it can simulate another Turing-complete model of computation. This is, in fact, how most Turing-complete models of computation are proven to be Turing-complete. Usually, the proof is not done using Turing Machines but using some other, more mathematically "simple" Turing-complete model of computation such as Rule 110, Conway's Game of Life, Cyclic Tag Systems or other Tag Systems, or even by implementing an interpreter for a simple Turing-complete programming language such as Brainfuck.

But since Halting Problem can't be solved by any programming language so every programming language should be Turing Incomplete. Right?

The Halting Problem is undecidable, which means the function $\mathit{Halts}(P, i)$ cannot be computed by a Turing Machine. That is the whole point of the Halting Problem.

Since $\mathit{Halts}(P, i)$ cannot be computed by a Turing Machine, it is irrelevant for determining Turing-completeness.

Note that Turing-completeness only refers to computable functions on the natural numbers. It does not refer to non-computable functions (such as $\mathit{Halts}(P, i)$), and it does not refer to operations which are not functions (such as printing, reading from a keyboard, launching a nuclear missile, etc.).

Also note that, according to the Church-Turing Thesis, the terms "effectively calculable", "computable", and "Turing-computable" are the same thing, meaning that everything that can be computed by a physically implementable machine at all can be computed by a Turing Machine, and, additionally, that the "intuitive" notion of "computable" is the same as the formal notion of "can be computed by a Turing Machine". Furthermore, this means that no model of computation that can be physically implemented can be more powerful than a Turing Machine.

So, in this particular sense, we can say that "something is Turing-complete if it can compute everything that can be computed at all". But that does not mean "compute any function" or "do any task".

But again, keep in mind that this only applies to computable functions on the natural numbers. For example, C++ can print to the screen, which a Turing Machine cannot. But that does not mean that C++ is more computationally powerful than a Turing Machine.

Some people have jokingly coined the term "Tetris-complete" or "Pacman-complete" to describe a programming language which can draw to the screen, receive asynchronous, interactive, input events, interact with the operating system, call third-party and system libraries, model the passage of time, etc. In other words: a programming language which can be used to implement real-world, interactive, macOS/Windows/Linux/Android/… (GUI) applications.

Most real-world programming languages are both Turing-complete and Tetris-complete, whereas the models of computation we are often talking about when discussing Turing-completeness are often not Tetris-complete: e.g., Turing Machines, λ-calculus, Rule 110, Tag Systems, etc.

OTOH, it is possible to have a programming language which is not Turing-complete but Tetris-complete. For example, it is possible to model event-driven interactivity as finite co-recursion over co-data rather than infinite recursion over data.

$\endgroup$
9
  • 1
    $\begingroup$ Additional info: The OP is probably referring to the common saying that "A Turing Machine can calculate any algorithm". en.wikipedia.org/wiki/Turing_machine which came from Turings proof that "a Turing Machine can calculate any sequence" en.wikipedia.org/wiki/Universal_Turing_machine This is NOT the same as "can do any task" $\endgroup$ Aug 18, 2023 at 16:30
  • $\begingroup$ Thanks. I expanded on some of the points. $\endgroup$ Aug 18, 2023 at 17:44
  • $\begingroup$ Re: things like "print to the screen" and other real-world engineering considerations: a fun term for that is "Tetris complete" - if the language and system can run the game Tetris, which has real-time performance and timing/delay requirements, graphics, and interactive keyboard input for single keypresses. $\endgroup$ Aug 18, 2023 at 18:40
  • $\begingroup$ If launching a nuclear missile is a side-effect of your function it should most definitely be documented! $\endgroup$
    – pipe
    Aug 18, 2023 at 19:12
  • 1
    $\begingroup$ @PeterCordes: I used that term here cs.stackexchange.com/a/64038/6729 and here cs.stackexchange.com/a/86171/6729, thanks for reminding me of that term! Indeed, that seems a good addition. (Unfortunately, I mis-rembered: Brady calls Idris Pac-man complete, not "Tetris-complete". And in good CS fashion, this has been proven by implementing Space Invaders and arguing that you can reduce one to the other.) $\endgroup$ Aug 18, 2023 at 22:21
4
$\begingroup$

Disclaimer: Please double check everything in this answer, because I am no expert on the topic.

The Halting problem is not a necessary condition for Turing completeness. On the contrary: the Turing machine itself cannot solve the halting problem. If You did build a "machine" that could solve the halting problem for Turing machines, it would be, at least in that sense, more powerful than a Turing machine. It would be unlike anything that we think of as computers. It would be "magic".

So what does a programming language have to do to be Turing complete? It has to be able to simulate a Turing machine. To prove that, it is sufficient to write a program that simulates any Turing complete "machine", e.g. lambda calculus.

So is C++ Turing complete? Yes but it is complicated. A Turing machine has an infinitely long Tape of memory. C++ on the other hand is very much designed for finite memory. Address pointers use a fixed number of bits, which is determined at compile-time at the latest. So you cannot simply use a (doubly) linked list to simulate the tape. In other languages with a more abstract memory reference model, like Java, this is very much possible.

So how can You prove that C++ is Turing complete? You can show that any program written in lambda calculus can be translated to C++. It is not quite a simple one-to-one translation because in C++ you will have to make some extra efforts to make recursion lazy. That being said that is enough to prove that C++ is Turing complete. All you need now is a computer with infinite memory with an instruction set that allows infinite recursion and a compiler that compiles to that architecture...

Fun fact: C++ is even Turing complete during compilation thanks to template-level programming. One implication is that we cannot even determine if compilation halts.

The memory limit is, of course, more of a theoretical limitation. Writing a range of length $n$ bits to the tape, the Turing machine requires at least $n$ iterations. To write to an infinite amount of memory takes an infinite amount of time. Ain't nobody got time for that! Alternatively, You could run the machine at an infinite clock frequency, in which case you will likely run into physical limitations. So for our finite lives, finite memory is just fine.

$\endgroup$
4
  • 1
    $\begingroup$ It’s an excellent answer. One quibble is that your argument that you can’t represent an unbounded tape in C++ also applies to lambda expressions, which could grow to any size. I like that you present Java as being a better example of a Turing-complete language — although for Java you’d have to change the semantics of new, so that it can’t throw an out of memory error. $\endgroup$ Aug 20, 2023 at 22:56
  • 1
    $\begingroup$ Are You sure? Somehow I thought as long as You avoid any pointers or memory addresses, e.g. as seen in this CppCon Lightning Talk, then you should be able to build a specialized compiler that can handle it. In practice You are absolutely right of course. $\endgroup$
    – DirkT
    Aug 21, 2023 at 7:12
  • 1
    $\begingroup$ As far as I understand it, the Java runtime, not the language, decides when to throw an OutOfMemoryError. I can run the same byte code on a 32 bit and a 64 bit machine and it can use all the memory (e.g. using linked lists). So all You have to do is to build a JVM with pointers of variable bit-length and Your byte code should run just fine on countably infinite memory. $\endgroup$
    – DirkT
    Aug 21, 2023 at 7:17
  • 1
    $\begingroup$ (a) No, I’m not sure. By using C++ lambdas and capturing values, it seems plausible. I hadn’t thought of that. (b) Yes. A JVM implementation that never throws a memory out of bounds error would be Turing complete, but Java is not Turing complete, as it’s specification allows new to fail. $\endgroup$ Aug 22, 2023 at 1:36
1
$\begingroup$

Short answer:

  • no machine can solve the Halting problem, this is a mathematical impossibility.

  • a system is called Turing-complete when it is able to simulate a Turing machine.


It is an easy matter to program a Turing machine in C. Strictly speaking, anyway, the simulation cannot be perfect because a physical system does not have infinite resources.

$\endgroup$
3
  • $\begingroup$ It's certainly a short answer. But it doesn't really seem to explain what's wrong with the syllogism in the question. $\endgroup$ Aug 19, 2023 at 4:17
  • 3
    $\begingroup$ Bullet 1 isn't correct. There is no proof that no machine can solve the halting problem; just that no Turing machine can. It is conjectured that no machine can, but not proven. $\endgroup$ Aug 19, 2023 at 4:30
  • $\begingroup$ @OscarSmith: in fact, all the discussion rests on what we call a machine. I didn't want to clutter my answer with Church's thesis. $\endgroup$
    – user16034
    Aug 19, 2023 at 10:02
-1
$\begingroup$

The if-statement alone is fully Turing complete for any computation that can be performed, so while it would not be efficient or pretty you could write any program purely with if-statements. I think that a lot of the meaning around this term has kind of taken on a sort of extended meaning that is more like saying "can this computer write a program as if it were human" or some variation of A.I. is implied. The simple fact of the matter is that A.I. is not physically or logically possible at least within a digital computer system. The requirement of every computer is to have a predictable instruction set which is mutually exclusive to free will or arbitrary behavior, they can not mix without destroying the thing that makes it "a computer" in the first place.

Regarding the halting problem, it can be solved by any program that has the potential to be halted, it is just not something we can easily forecast or reduce the computational work so as to run a simulator in fast-forward, but in their own time each program will solve it's halting status or run indefinitely, we just can't look ahead in time with that type of problem because it's inputs and conditions rely on unknown future conditions, so it is inherently a necessarily expensive computation to perform when determining if a program will encounter a deadlock or crash.

You could design a language that has this capability to know it's future halting status or potential, but in creating the bounds needed to construct that type of language we would need to remove it's turing completeness to some degree so that it operates within a finite set of possible conditions... the trade off is diversity in the language's complexity for ability of the compiler to forecast something like a halting condition.

$\endgroup$
2
  • 1
    $\begingroup$ Any model of computation without some equivalent of loops or recursion cannot be Turing-complete because there are a finite number of paths through the computation. $\endgroup$
    – Pseudonym
    Aug 19, 2023 at 5:06
  • 1
    $\begingroup$ The thing about if almost right. The actual correct statement is: the instruction goto x if --y <= 0 is fully Turing Complete. That single instruction has been proven to be able to add numbers together, to generate primes and most importantly you can implement a Universal Turing Machine using a CPU/language with only that instruction. $\endgroup$
    – slebetman
    Aug 19, 2023 at 15:04

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.