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 ...
- 5,870
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 ...
- 14.4k
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, ...
- 5,870
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 ...
- 3,241
40
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 ...
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 ...
- 81.4k
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.♦
- 156k
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 ...
- 5,870
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 ...
- 81.4k
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 ...
- 29.7k
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 ...
- 887
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?
- 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 ...
- 1,033
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 ...
- 5,870
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.♦
- 156k
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 ...
- 275k
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 ...
- 5,931
14
votes
Accepted
Is Desmos Turing-Complete?
I tried various things with Desmos and came to the following conclusions:
Desmos without Actions is not Turing-complete.
All built-in functions are halting (basically since they are mathematical in ...
- 396
13
votes
Accepted
Connection between NAND gates and Turing completeness
There is indeed little connection. For a thorough understanding, let me explain the connection between programs and circuits.
A program (or algorithm, or machine) is a mechanism for computing a ...
- 275k
13
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 ...
- 303
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 ...
- 29.7k
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 ...
- 246
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 ...
- 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.
- 30k
12
votes
Is there an algorithm for converting Turing machines into equivalent Lambda expressions?
All proofs of the equivalence of these two models of computation are constructive, that is they describe an algorithm for converting a program from one model of computation to the other. However, I ...
- 275k
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 ...
- 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 ...
- 72.1k
10
votes
Accepted
Is there an algorithm for converting Turing machines into equivalent Lambda expressions?
Sure there is. I'm going to assume you can figure out how to convert Haskell into the lambda calculus; for a reference, look at the GHC implementation.
Now just to be clear: a Turing Machine is a (...
- 394
10
votes
Is there an algorithm for converting Turing machines into equivalent Lambda expressions?
Since you did not like Yuval's answer, you deserve this one:
The equivalence of Church's $\lambda$-calculus and Turing machines is proved in the Appendix of Alan Turing's 1937 paper On computable ...
- 30k
10
votes
Does a do-while loop suffice for Turing-completeness?
I don't know Brainfuck so you'll have to do some translation from my pseudocode. But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply.
do-while is equivalent to while-...
- 81.4k
Only top scored, non community-wiki answers of a minimum length are eligible