Question Detail: 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?
Asked By : Khanzor
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/991
Answered By : Raphael
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:
- The constant $0$ function
- The successor function
- Selecting parameters
- Function composition
- Primitive Recursion
- 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
- The constant 0
- Incrementation _ + 1
- Variable access x
- Program/statement concatenation _; _
- Countdown loops for ( x to 0 ) do _ end
- While loops while ( x != 0 ) do _ end
