71
$\begingroup$

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?

$\endgroup$
3

6 Answers 6

56
$\begingroup$

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
$\endgroup$
3
  • 1
    $\begingroup$ I think it's obvious that you cannot drop the 5th rule in the language. Since the while loop in 6 compares to the constant zero, variables can only be incremented by rule 2 and there are no negative constants to start from (rule 1), the while loop in 6 is either not entered (x=0) or it's infinite (x>0, and loop body cannot decrease it). $\endgroup$
    – MSalters
    Feb 3, 2015 at 11:03
  • 2
    $\begingroup$ @MSalters I think you are right; for the simulation I seem to have had in mind, we need _ - 1 and I can not think of a way to implement that without for. Thanks for catching that! (What is "better" -- including _ - 1 or for? Hmm.) $\endgroup$
    – Raphael
    Feb 3, 2015 at 12:39
  • $\begingroup$ @Raphael: Not to intrude on a long-forgotten thread, but to my mind, "the language must have a decrement" feels like a much more natural requirement than "the language must be able to express two different kinds of loops, one of which coincidentally causes a variable to be decremented." But that's just my personal taste. $\endgroup$
    – Kevin
    May 7, 2023 at 3:48
28
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ The only part I'm not certain on is your answer to the minimal set of necessary operations. You seem to limit your definition of operations to Control Structures which seems to be a much narrower scope than asked, and beyond your own requirement of not defining them "so vaguely, that [they] become meaningless". $\endgroup$ Apr 2, 2012 at 20:52
  • $\begingroup$ @JoshuaDrake I'm not sure what you mean. I'm not limiting operations to control structures. It's just that I don't talk about any operations that aren't control structures in my counter example because they're not relevant to the example. Actually I do mention "a way to store arbitrary amounts of data" - that's hardly a control structure. $\endgroup$
    – sepp2k
    Apr 2, 2012 at 21:01
  • $\begingroup$ You make the point that some languages support Turing Completeness with goto but that some do not, seemingly claiming that because some use it and some do not that goto then cannot be part of a set of operations required for Turing completeness. My point is that goto is simply a syntactical way of implementing a particular more generic operation, such as a jump. Therefore I believe that if you simply abstracted away from specific control structures you would move closer to a set of operations that would at least point toward Turing Completeness. $\endgroup$ Apr 3, 2012 at 11:47
  • $\begingroup$ @JoshuaDrake I don't think using "jump" instead of goto gets us to the point where we can define a sufficient and necessary set of operation. It's probably true that every language would need some sort of jump operation (and if it's only function calls), but I don't think you'll be able to come up with further operations to make it sufficient. For example the lambda calculus has two operations: application (i.e. our jump operation) and abstraction (i.e. creating functions)... $\endgroup$
    – sepp2k
    Apr 3, 2012 at 11:57
  • 1
    $\begingroup$ @JoshuaDrake I don't think the article is trying to claim that any Turing-complete language needs to have those operations. Especially since it specifically restricts that statement to procedural languages. Except for a form of goto (i.e. function application) the Lambda Calculus doesn't have any of those things. I think "minimum" here only means that in a language that only has those features, you can't remove any of them without losing Turing completeness. Not that there's no other minimal set of operations that is also sufficient for Turing completeness. $\endgroup$
    – sepp2k
    Apr 3, 2012 at 12:33
19
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
0
17
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.