Skip to main content
82 votes
Accepted

Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that. A list is not a natural number, and list ...
Jörg W Mittag's user avatar
71 votes
Accepted

Why are some programming languages Turing complete but lack some abilities of other languages?

Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it. This says nothing about the ...
chi's user avatar
  • 14.6k
54 votes
Accepted

Are all turing complete languages interchangeable

Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model. So, ...
Jörg W Mittag's user avatar
49 votes

Why are some programming languages Turing complete but lack some abilities of other languages?

Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do. This does ...
Cort Ammon's user avatar
  • 3,351
41 votes
Accepted

Is C actually Turing-complete?

I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here. In most ...
Gilles 'SO- stop being evil''s user avatar
39 votes

What does being Turing complete mean?

It's not tautological at all. A model of computation is Turing-complete if it can simulate all Turing machines, i.e., it is at least as powerful as Turing machines. One thing that Turing machines ...
David Richerby's user avatar
38 votes
Accepted

Does the Turing test have anything to do with Turing completeness or Turing machines?

No, there is no relationship. The connection is that they are both based on concepts/work by Alan Turing, who was an early pioneer who made many advances.
D.W.'s user avatar
  • 160k
33 votes
Accepted

Can we ever achieve Turing completeness?

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 ...
Jörg W Mittag's user avatar
29 votes
Accepted

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying ...
David Richerby's user avatar
26 votes

Why are some programming languages Turing complete but lack some abilities of other languages?

Think of programming languages as different land vehicles: bicycles, cars, hovercars, trains. Turing Completeness says "this vehicle can go anywhere any other vehicle can go." That is, you can ...
Joey Eremondi's user avatar
24 votes

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

There is an important class of primitive recursive functions. Citing Wikipedia, [P]rimitive recursive function is roughly speaking a function that can be computed by a computer program whose loops ...
Ivan Smirnov's user avatar
20 votes

How Turing Machine Can Never Stop?

Step 3 could be phrased more properly as "If M has already stopped by the time we get to N steps, accept". Does that help to clarify?
Christian's user avatar
  • 201
19 votes

Are Finite Automata Turing Complete?

No finite automaton can simulate a Universal Turing machine, so finite automatons are not Turing complete. This falls out immediately from them having a finite number of states. Universal Turing ...
Curtis F's user avatar
  • 1,043
17 votes

Why are some programming languages Turing complete but lack some abilities of other languages?

What you are essentially asking about is the difference between the computational power and what is commonly called the expressive power (or just expressiveness) of a language (or system of ...
Jörg W Mittag's user avatar
17 votes
Accepted

Is a machine Turing-complete when it can decide a context-sensitive language?

No. Context-sensitive languages can be recognized by linear-time nondeterministic Turing machines, which are not Turing complete. The ability to recognize a recursively enumerable set also does not ...
D.W.'s user avatar
  • 160k
16 votes

What does being Turing complete mean?

Turing's model of computation is just one of many equivalent models of computation. It has the same power as Gödel's recursive functions and Church's lambda calculus, which were proposed around the ...
Yuval Filmus's user avatar
15 votes
Accepted

How is PowerPoint Turing complete?

Some system is Turing complete if you can simulate every Turing machine inside of it. Powerpoint is Turing complete because its animation features can be used to simulate a Turing machine. This video ...
adrianN's user avatar
  • 5,951
15 votes
Accepted

Is Desmos Turing-Complete?

Update (2024-04-23): Recursion is now available. A recursive function can take a list parameter, so we can implement a tag system using it. Ignoring technical limitations (recursion depth limit), this ...
Bubbler's user avatar
  • 406
14 votes

Is C actually Turing-complete?

C99's addition of va_copy to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic ...
feersum's user avatar
  • 313
13 votes
Accepted

Is there a way to test "Turing completeness"?

I don't know about specific models. It's pretty easy to become Turing Complete, since all you need is infinite search. So I can imagine a model where searching for finite vs. infiniteness boils down ...
Joey Eremondi's user avatar
13 votes
Accepted

Looping and branching with Algorithmic Differentiation

AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be ...
Markus Mottl's user avatar
13 votes
Accepted

What does being Turing complete mean?

I pondered a while whether to add yet another answer. The other answers focus on the middle of his question (about "turing complete", "tautology" and so on). Let me grab the first ...
AnoE's user avatar
  • 1,273
13 votes

Is English Turing-complete?

English is neither a language with a given operational semantics nor a model of computation of any other kind. Your question does not make sense.
Andrej Bauer's user avatar
  • 30.4k
12 votes

How many pairs of brackets are sufficient to make Brainfuck Turing complete?

I'm not 100% sure that it's impossible to do this with two sets of brackets. However, if the cells of the BF tape allow unbounded values, three sets of brackets are enough. (For simplicity, I'll also ...
ais523's user avatar
  • 248
11 votes
Accepted

Can one consider living (biological) cell to be Turing Complete?

Every living organism has -- to our knowledge -- only a finite amount of resources available. So no, they can not be Turing-complete. That said, there is quite a number of bio-inspired models of ...
Raphael's user avatar
  • 72.4k
11 votes

Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?

No, it doesn't require that. These are two orthogonal issues. You can easily define a new programming language where you provide fully defined semantics for all operations; yet it can be Turing ...
D.W.'s user avatar
  • 160k
10 votes

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

Any Turing-complete computational model that does not have modifying code (or "code") serves as a proof of that statement. I don't know that any of the standard models (TM, RAM, ...) do have modifying ...
Raphael's user avatar
  • 72.4k
10 votes
Accepted

Can the human brain be considered Turing complete?

Let's do this in order: We do not say "another Turing complete language's algorithm" because "language's algorithm" is at best a confusing phrase. You might have meant "language's interpreter" but we ...
Andrej Bauer's user avatar
  • 30.4k
10 votes
Accepted

How many pairs of brackets are sufficient to make Brainfuck Turing complete?

This is a further development of @ais523's answer, reducing it to only two sets of brackets, and also using a more compact cell placement based on Golomb ruler theory. ais523 has made a compiler for ...
Ørjan Johansen's user avatar
9 votes
Accepted

Is the system of measuring length in the US Turing complete?

The post you're referring to is a joke: the US (and similar British Imperial) measurement systems are not Turing complete and the claim is an example of hyperbole. A key feature that's necessary for ...
David Richerby's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible