Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 11 down vote favorite
3

What is the minimal set of language features/structures that make it Turing-complete?

share|improve this question
9  
Won't it be better to just google it? en.wikipedia.org/wiki/Turing_completeness – aml90 Jan 29 '12 at 17:04
1  
Hi Curious Cat, welcome to Programmers! Calls for lists aren't on-topic here: I've removed that part out of your question. That said, this quest is extremely broad: is there a specific problem you're working on that has you thinking about Turing-completeness? – user8 Jan 29 '12 at 21:02
1  
@amalantony: Just as a footnote‌​. – Bobby Jan 30 '12 at 9:24

3 Answers

up vote 20 down vote

A Turing tarpit is a kind of esoteric programming language which strives to be Turing-complete while using as few elements as possible. Brainfuck is perhaps the best-known tarpit, but there are many.

  • Iota and Jot are functional languages with two and three symbols, respectively, based on the SK(I) combinator calculus.

  • OISC (One Instruction Set Computer) denotes a type of imperative computation that requires only one instruction of one or more arguments, usually “subtract and branch if less than or equal to zero”, or “reverse subtract and skip if borrow”. The x86 MMU implements the former instruction and is thus Turing-complete.

In general, for an imperative language to be Turing-complete, it needs:

  1. A form of conditional repetition or conditional jump (e.g., while, if+goto)

  2. A way to read and write some form of storage (e.g., variables, tape)

For a lambda-calculus–based functional language to be TC, it needs:

  1. The ability to abstract functions over arguments (e.g., lambda abstraction, quotation)

  2. The ability to apply functions to arguments (e.g., reduction)

There are of course other ways of looking at computation, but these are common models for Turing tarpits. Note that real computers are not universal Turing machines because they do not have unbounded storage. Strictly speaking, they are “bounded storage machines”. If you were to keep adding memory to them, they would asymptotically approach Turing machines in power. However, even bounded storage machines and finite state machines are useful for computation; they are simply not universal.

Strictly speaking, I/O is not required for Turing-completeness; TC only asserts that a language can compute the function you want, not that it can show you the result. In practice, every useful language has a way of interacting with the world somehow.

share|improve this answer
up vote 5 down vote

From a more practical standpoint: if you can translate all programs in a Turing-complete language into your language, then (as far as I know), your language must be Turing-complete. Therefore, if you want to check whether a language you designed is Turing-complete, you could simply write a Brainf*** to YourLanguage compiler and prove/demonstrate that it can compile all legal BF programs.

To clarify, I mean that in addition to an interpreter for YourLanguage, you write a compiler (in any language) that can compile any BF program to YourLanguage (keeping the same semantics, of course).

share|improve this answer
3  
Yes, that would definitely be the most practical way to approach it. </sarcasm> – Robert Harvey Jan 29 '12 at 18:27
2  
@RobertHarvey has a point, but the general idea is quite vital. Brainfuck is proven to be turing-complete and very simple as programming languages go. For non-esoteric programming languages, implementing a brainfuck interpreter may be much easier and faster than giving a rigorous proof out of nowhere (I can implement BF in a couple of lines of Python, but I'm not sure where to start with a formal proof that Python is turing complete); and dozens of esoteric brainfuck-inspired languages are known to be turing complete because it's known how they map to brainfuck. – delnan Jan 29 '12 at 18:53
4  
@RobertHarvey: Why not? Surely someone designing their own language would be able to write a BF compiler to it (if it was imperative, and find a suitable other language otherwise). – Anton Golov Jan 29 '12 at 18:53
1  
@sepp2k - I think I didn't express myself clearly, please see the edit. – Anton Golov Jan 29 '12 at 20:07
@AntonGolov Actually you did express yourself clearly, I just can't read properly. Nevermind me then ;-) – sepp2k Jan 29 '12 at 20:12
show 1 more comment
up vote 0 down vote

You just need conditional branching (to simulate automata within the machine) and variables (to simulate tape). All general purpose programming languages and modern machine instruction sets are Turing complete, apart from having finite memory.

share|improve this answer
2  
You need more than just "variables": to simulate a Turing machine you must be able to represent an unbounded amount of data, so you need something like dynamic allocation. If the amount of information you can represent is bounded, you just have a huge finite state machine, not a Turing machine. All actual computers are finite, but a language definition may be Turing complete, depending on how it is defined. Any implementation on a physical machine is a finite approximation, though. – Ryan Culpepper Jan 29 '12 at 18:58
@RyanCulpepper that's why I wrote "apart from having finite memory". – Randolf R-F Jan 29 '12 at 19:08
@Sheldon Ryan's point was that any language that is considered turing complete would be able to run any decidable program when run on a hypothetical computer with infinite memory. A language that only has variables and conditional branching, but no memory allocation or recursion would not though. So such a language is not turing complete. (Also the language would also need some way to modify the value of a variable or having variables would be rather pointless). – sepp2k Jan 29 '12 at 19:40
1  
Conditional branching isn't enough; you also need loops of some sort which can be done with if and goto. Intercal's [PLEASE] COME FROM ... UNLESS ... is adequate, since the COME FROM statement can come before the statement it refers to. – David Thornley Jan 30 '12 at 14:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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