This is a very interesting question.. In our world, it doesn't really have any practical consequences. Making a Turing complete language is trivial, you only ne

This is a very interesting question.. In our world, it doesn't really have any practical consequences. Making a Turing complete language is trivial, you only need increment/decrement, zero and a jump instruction. These things are available on just about any platform. Given infinite memory (which in practice means an infinite number of states), any particular Turing machine computation can be performed by a specifically constructed pushdown automation or even a finite-state machine. The distinction between the capabilities of Turing machines and less general machines is in what types of computation one particular machine description can perform. There is a particular Turing machine that can simulate any Turing machine (taking a machine description and input for this machine as input), so obviously any Turing computation can be performed by this particular machine. It would probably be really difficult to program an FSM or a PDA to perform "general" computations, but it would be an interesting intellectual exercise. Try making a programming language (with LISP macros, maybe?) that will let you easily describe a finite-state machine to solve a particular computational problem. Given an infinite amount of code and memory, you could do everything a Turing machine could do. It's like the recent discussion around the halting problem: how much of a problem is it really in the practical world? You can always design a mathematical contradiction around the general case, but for any particular problem it is possible to describe a solution that works. The difference is that any practical benefit of using a language that is not Turing complete is hid very well.