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


70

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


55

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


41

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


36

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


23

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


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


22

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


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

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

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


12

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


12

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


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


10

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 numbers ("State 1", "State 2", "State 3", etc.). Even with just two non-blank characters, the universal machine can represent all those integers as binary strings. ...


10

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-do. do X while Y is equivalent to X; while Y do X and, assuming you have conditionals, while Y do X is equivalent to if Y then (do X while Y). Life is a bit ...


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