The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

## Hot answers tagged turing-completeness

69

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 language features. A Turing Machine has very limited compositional features. The untyped $\lambda$-calculus is far more compositional, but lacks many features ...

56

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, what are the computations a Turing Machine can model? Well, first and foremost, Alan Turing and all of his colleagues were only ever interested in functions on ...

48

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 not, however, say how convenient it is to do so. Some features that are easy in some languages may be very difficult in others, due to design choices. Turing ...

45

I always though that $\mu$-recursive functions nailed it. Here is what defines the whole set of computable functions; it is the smallest set of functions containing resp. closed against: The constant $0$ function The successor function Selecting parameters Function composition Primitive Recursion The $\mu$-operator (look for the smallest $x$ such that...) ...

40

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 which can be recognized using a context-free grammar". A way of specifying a computation. "Turing-complete language" means "a way of specifying programs in which ...

38

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 can do is simulate other Turing machines (via the universal Turing machine). That means that, if your model of computation can't simulate Turing machines, it can'...

34

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 programming languages, you can simulate a Turing machine by: simulating the finite automaton with a program that uses a finite amount of memory; simulating ...

29

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 program is now the interpreter's data. In particular, you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its ...

26

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 compute all the same functions. Input to output, start to end. But, that statement says nothing about how you get there. It might be on rails, it might be on roads, ...

21

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 clear criteria. The name has no meaning beyond its official semantics. Imperative languages are not based on Turing machines. They are based on RAM machines. ...

20

Does there exist a set of computations that need to be performable in a programming language in order for it to be considered Turing Complete? Yes, in order to be considered Turing complete a programming language needs to be able to perform any computation that can be performed by a Turing machine. So as a minimum requirement one might say, you need to be ...

20

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 Turing machine) is the concept of an explicit memory that can be modified to store (intermediate results). It is an automata view of computation, with a concept ...

18

It's a fairly reliable rule of thumb that Turing-completeness depends on the ability to construct answers or intermediate values of unrestricted "size" and the ability to loop or recurse an unrestricted number of times. If you have those two things, you probably have Turing-completeness. (More specifically, if you can construct Peano arithmetic, then you ...

17

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 computation). Computational Power The computational power refers to what kinds of problems the language can compute. The most well-known class of computational power is ...

17

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 same time, as well as other models such as the pointer machine. You can therefore state that A computer is Turing-complete if it can solve any problem that ...

15

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 machines require an unbounded amount of space to work. The source code of an Iota program can be recognized with a finite automaton. That automaton doesn't evaluate ...

14

There are various single instructions that lead to Turing complete languages. The typical example is "subtract and branch if zero". These are well known in the context of assembly language programming. See the Wikipedia article for details. This leads to a characterization: a language is Turing complete if and only if it is able to simulate the operations ...

13

The combinators $\mathbf{S}$ and $\mathbf{K}$ where, $(\mathbf{S}\ x\ y\ z) = (x\ z\ (y\ z))$ and $(\mathbf{K}\ x\ y) = x$ are sufficient to express any (closed) lambda term, therefore any computable function. See this wikipedia page for details. In fact, the lambda term $\mathbf{X}=\lambda x.((x\ \mathbf{S})\ \mathbf{K})$ is a sufficient basis to express ...

13

This isn't a general answer to your question, but by the structured programming theorem, all that is needed is the ability to do selection (e.g., if in C/C++) and repetition (e.g., while in C/C++). Edit: as pointed out by Dave Clarke in the comments, the structured programming theorem also requires sequence. I didn't initially list this since I took for ...

13

Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like $P = BQP$). To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary $\... 13 The informal statement is not true, as shown by the following programming language. Any string of, say, ASCII characters is a valid program and the meaning of every program is, "Output a program that just outputs a copy of its input." Thus, every program in this language is a compiler for the language but the language is not Turing-complete. I'm not sure ... 13 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 and last part, and thus the bigger and slightly philosophical picture: But what does it mean? What does being Turing complete mean? Is there a way to define the ... 12 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 caution you that these proofs are probably rather informal, and may not satisfy you. You may get luckier if you consult original work by computing pioneers (... 12 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 to Turing Completeness, but I don't know if any actually exist. But a general algorithm "look at an arbitrary systems and tell if it's Turing Complete" can't ... 12 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 assume that we can move the tape head left past its starting point, although because this construction only uses a finite region of the tape, we could lift that ... 11 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", and "outputs" the correct answer. (Note that Turing machines don't make an appearance here: they are just one example of a universal computation model.) The ... 11 In a functional programming language that is powerful enough (for example, with data types to implement closures) you can eliminate all uses of higher order by the transformation of defunctionalization. Since this method is used to compile this kind of language, you can reasonably assume that this does not affect performances and that in this setting higher ... 11 Every language that can implement two counters$C_1, C_2$(i.e. two registers that can store two arbitrarily large integers) and a program made with a labeled sequence of these two elementary instructions is Turing complete: ADD$1$to counter$C_i$, GOTO instruction$I_j$SUBTRACT$1$from counter$C_i$if$C_i > 0$and GOTO instruction$I_j$; ... 11 A special case of model theory is finite model theory which is closely related to complexity theory and database theory. However the methods being used in classical model theory (e.g. types, stability theory, forcing, large cardinals etc) are geared towards infinite models and assume compactness. Hence they don't appear to be useful in computer science. A ... 11 Your misunderstanding is: 'sure' in the sense of being computationally verified by an algorithm We are not, and we can not be . The question, Is this given Turing machine$M\$ a universal one? can not be generally and algorithmically decided for the reasons you state. However, we can prove for a fixed Turing machine that it is universal -- and that ...

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