What is the minimal set of language features/structures that make it Turing-complete?
A programming language is turing complete if you can do any calculation with it. There isn't just one set of features that makes a language turing complete so answers saying you need loops or that you need variables are wrong since there is languages that has neither but are turing complete.
Alan Turing made the universal turing machine and if you can translate any program designed to work on the universal machine to run on your language it's also Turing complete. This also works indirectly so you can say language X is turing complete if all programs for turing complete language Y can be translated for X since all universal turing machine programs can be translated to a Y program.
The time complexity, space complexity, easy of input/output format and easy of writing any program is not included in the equation so such machine can theoretically do all calculations if the calculations are not halted by power loss or Earth being swallowed by the sun.
Usually to prove turing completeness they make an interpreter for any proven to be turing complete language but for it to work you need means of input and output, two things that are really not required for a language to be turing complete. It's enough that your program can alter it's state at startup and that you can inspect the memory after the program is halted.
To make a successful language it needs more than turing completeness though and this is true for even turing tarpits. I don't think BrainFuck would have been popular without
i know this is not the formally correct answer, but once you take the 'minimal' out of 'Turing-complete' and put 'practical' back where it belongs, you'll see the most important features that distinguish a programming language from a markup language are
to test these assertions, start out with a markup language, say, HTML. we could invent an HTML+ with variables only, or conditionals only (MS did that with conditional comments), or some kind of loop construct (which in the absence of conditionals would probably end up as something like
the quest for minimality in logic and programming sure is important and interesting, but if i had to teach n00bies young or old 'what is programming' and 'how to learn to program', i'd hardly start out with the full breadth and width of the theoretical foundations of Turing completeness. the whole essence of cooking and programming is doing stuff, in the right order, repeating until ready, as your mom did it. that about sums it up for me.
then again, i never finished my CS.
In general, for an imperative language to be Turing-complete, it needs:
For a lambda-calculus–based functional language to be TC, it needs:
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.
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).