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 ...
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.2k
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, ...
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,223
45 votes
Accepted

Can regular languages be Turing complete?

In short, the answer is yes. But you're mixing two completely unrelated meanings of the term "language" (yes, this is confusing): A set of strings. "Context-free language" means "a set of strings ...
  • 2,229
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 ...
38 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 ...
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 ...
26 votes
Accepted

Why are functional languages Turing complete?

In a nutshell: What characterizes imperative programming languages as close to Turing machines and to usual computers such as PCs, (themselves closer to random access machines (RAM) rather than to ...
  • 19.2k
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.4k
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 ...
23 votes

Why are functional languages Turing complete?

Turing-complete is just a name. You can call it Abdul-complete if you want. Names are decided upon historically and are often named after the "wrong" people. It's a sociological process that has no ...
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,003
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 ...
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 ...
15 votes
Accepted

How is the rule 110 Turing complete?

Universality is a somewhat informal notion. What it roughly means is that for each computable function $f$ there is a "program" $P$ in the model so that "running" $P$ on any input $x$ always "halts", ...
14 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,910
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 ...
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,165
13 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 ...
  • 386
12 votes

Why are functional languages Turing complete?

Because "Turing-complete" just means "it can compute whatever a Turing machine can compute."
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 ...
12 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.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 ...
  • 248
11 votes

Can regular languages be Turing complete?

While the set of legal programs in Jot is regular, Jot itself is Turing-complete. That means that each computable function can be expressed in Jot. We can even come up with a language in which all ...
11 votes

Can we write algorithms without conditional statements?

Here is a Turing complete "programming" language. It has just two constants, called $K$ and $S$, and one operation called "application", written $x \cdot y$. The two constants satisfy the rules $$(K \...
  • 28.9k
11 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 ...
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 ...
  • 71.5k
10 votes
Accepted

How can a universal Turing machine simulate "bigger" ones?

The answer to both subquestions is the same: by using the tape to store the necessary data. We can assume that the state set and alphabet of the machine to be simulated are subsets of the natural ...

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