# Tag Info

## Hot answers tagged turing-completeness

82

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 intersection is not a function on natural numbers. Note: it is, of course, possible to encode lists as natural numbers, which would then make list intersection a ...

71

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 ...

54

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 ...

49

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 ...

44

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

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 ...

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'...

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, ...

24

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 ...

24

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 are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). They are powerful ...

23

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. ...

22

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 ...

20

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?

18

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 Jot program can be recognized with a finite automaton. That automaton doesn't evaluate ...

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 ...

16

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 ...

14

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 ...

14

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 ...

14

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 explains the proof for Powerpoint. You can read the proceedings from the 2017 SIGBOVIK for a written explanation.

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 ...

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

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 ...

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

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 binary strings are legal, but the language itself is Turing complete (exercise). You're confusing syntax and semantics. By the way, context-free languages are ...

11

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 \cdot x) \cdot y = x$$ and $$((S \cdot x) \cdot y) \cdot z = (x \cdot z) \cdot (y \cdot z).$$ This is known as a combinatory algebra and is well known to be ...

11

Because "Turing-complete" just means "it can compute whatever a Turing machine can compute."

11

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 computation that can be studied formally. Sticker systems [1], for instance -- an abstraction of recombining DNA fragments -- can be shown to reach Turing-power ...

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