What are practical guidelines for evaluating a language's "Turing Completeness"?
- by AShelly
I've read "what-is-turing-complete" and the wikipedia page, but I'm less interested in a formal proof than in the practical implications of being Turing Complete.
What I'm actually trying to decide is if the toy language I've just designed could be used as a general-purpose language. I know I can prove it is if I can write a Turing machine with it. But I don't want to go through that exercise until I'm fairly certain of success.
Is there a minimum set of features without which Turing Completeness is impossible?
Is there a set of features which virtually guarantees completeness?
(My guess is that conditional branching and a readable/writeable memory store will get me most of the way there)
EDIT:
I think I've gone off on a tangent by saying "Turing Complete". I'm trying to guess with reasonable confidence that a newly invented language with a certain feature set (or alternately, a VM with a certain instruction set) would be able to compute anything worth computing. I know proving you can building a Turing machine with it is one way, but not the only way.
What I was hoping for was a set of guidelines like: "if it can do X,Y,and Z, it can probably do anything".