Are there minimum criteria for a programming language being Turing complete?

Question

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete?

From what I can tell from wikipedia, the language needs to support recursion, or, seemingly, must be able to run without halting. Is this all there is to it?

Answer 1

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:

1. The constant $0$ function
2. The successor function
3. Selecting parameters
4. Function composition
5. Primitive Recursion
6. The $\mu$-operator (look for the smallest $x$ such that...)

Check above link for details; you see that it makes for a very compact programming language. It is also horrible to program in -- no free lunch. If you drop any of those, you will lose full power, so it is a minimal set of axioms.

You can translate those quite literally into basic syntactical elements for WHILE programs, namely

1. The constant 0
2. Incrementation _ + 1
3. Variable access x
4. Program/statement concatenation _; _
5. Countdown loops for ( x to 0 ) do _ end
6. While loops while ( x != 0 ) do _ end

Answer 2

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 able to implement an universal Turing machine - or an interpreter for any other Turing complete language - in it.

From what I can tell from wikipedia, the language needs to support recursion, or, seemingly, must be able to run without halting. Is this all there is to it?

No. For example a language where the only allowed operation is recursion (i.e. the only possible function you can write is f(x) = f(x)), is not Turing complete because all you can write in it are programs that never terminate. As I said earlier, a Turing complete language needs to be able to implement any computation that can be performed by a Turing machine. So clearly that does not suffice.

Also a language doesn't have to support recursion in the way you're thinking of. Just an unrestricted way of expressing loops. That might be recursion, but it might also be a while-loop or goto. A language that doesn't have functions at all can still be Turing complete. And again loops or recursive functions aren't a sufficient condition. You still need a way to execute different code depending on a condition and a way to calculate new values from old ones (otherwise all loops/recursion would either be infinite or not run at all).

---

As for whether there's a minimal set of of necessary and sufficient operations, such that any language that supports these operations is Turing complete and any language that doesn't is not: No, there isn't (unless you define "operation" so vaguely, that it becomes meaningless):

For example as I already said, there are Turing complete languages that don't support recursive functions (or any functions at all). Those can still be Turing complete if they have a goto statement or while loop (and a way to store arbitrary amounts of data). However a language with recursive functions needs neither while nor goto to be Turing complete. So goto would not be in the set of necessary sufficient operations, but there are languages that are no longer Turing complete if you remove goto. Thus there is no such set.

Answer 3

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 of fetching and storing integers in memory and performing the "subtract and branch if zero" operation on them.

Answer 4

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 granted the reader would understand that basic blocks of other instructions, such as those alluded to later for reading from and writing to the memory store, etc., were also necessary). It is, of course, better to be explicit; you need to be able to do these things, too.

Since both of these can be implemented using a conditional jump instruction (e.g., JNZ in x86), that is also sufficient for Turing-equivalence.

Note that other things are required, i.e., the ability to write an unbounded number of symbols (e.g., bits... 0 or 1) to some sort of external memory store. In that sense, real computers are not Turing equivalent, since none of them have an infinite amount of storage. The Turing model is still useful, though, since the amount of memory is typically huge, and even though any problem a real computer can solve can be solved by a deterministic finite automaton, using that model of computation isn't particularly useful (since the number of states would be preposterously huge).

Note that this isn't necessarily at odds with sepp2k's answer; this is sort of just a different way to think about the same question.

EDIT:

Note also that you don't really need both if and while in C/C++. You can simulate if using while as follows:

bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program

The following code is always equivalent:

bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program

Well... the construction should work and be possible if you're careful, that is. Note also that if you have recursive functions, you eventually need selection also; since recursive functions without selection can't really implement base cases, so any recursive function would result in infinite recursion.

EDIT:

Also, regarding your question as to whether the ability to write a program that doesn't halt is sufficient for Turing equivalence, the answer is no; it is necessary, but not sufficient. We can solve the halting problem for programs written in a language which cannot express programs that fail to halt; the answer is "the program does halt" for all instances. However, we can define a language where the only instruction causes the machine to enter an infinite loop... such a language isn't Turing-equivalent.

Answer 5

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 all lambda terms. See later in the same wikipedia page.

Answer 6

The language constructs are interchangeable

There is no set minimum criteria about what constructs must natively be provided by a programming language. If it provides some weird constructs that can somehow be convoluted to express a Turing-complete system, then apparently those constructs are "just as suitable" as any others.

To prove this - a language that provides only a "subtract and branch if zero" operation is Turing complete; there exist Turing complete languages that don't provide a separate "substract and branch if zero" construct, ergo there is no construct or a set of constructs that is mandatory.

The effects of any TP-complete language construct can be emulated by the constructs of any other TP-complete language.

Answer 7

This should at least be part of the answer to the question. And the answer is no.

Intuitively, a specification of programming language can be arbitrarily complex such that it may encode any decidable function, by intention or not. Therefore, any halting procedure by Rice's theorem will not be able to determine whether a programming language is Turing complete in general.

This brings the pursuit of minimal criteria for Turing completeness into two possible scenarios:

1. The criteria is too vague or too forgiving such that some of languages meeting the criteria are actually not Turing complete, or
2. The criteria is too strict or too specific such that some of the Turing complete languages are mistakenly ruled out.