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

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?

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

StackExchange Computer Science Q#991, answer score: 56