What are practical guidelines for evaluating a language's "Turing Completeness"?

Posted by AShelly on Stack Overflow See other posts from Stack Overflow or by AShelly
Published on 2009-01-15T23:48:34Z Indexed on 2010/04/04 15:53 UTC
Read the original article Hit count: 321

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".

© Stack Overflow or respective owner

Related posts about turing-complete

Related posts about language-design