Hello everyone. I recently came accross the concept of Turing completeness (in languages). I was wondering, is there a general method for determining if a language is Turing complete? Or is it one of those intuitive things where you just have to look at it for a while and go "oh yes" (or "oh no)? When I say a general method I mean a mathematical proof. This isn't a support question, I'm just curious. Any answers appriciated.
Steven.
Yes. Show that any program written in language X can be written in language Y, where X is a known Turing-complete language. A convenient way to do this is to write an interpreter for X. A convenient choice for X is Brain****. If you can write a Brain**** interpreter in a language, then that language is Turing complete.
Of course, no language run on computers is _truly_ Turing-complete, because computers have limited memory (this makes them, theoretically-speaking, equivalent to deterministic finite automata).
See
http://www.cs.rpi.edu/~buschc/course.../schedule.html for more details. These are slides from a class I'm taking. I think the slides are quite good (since I've only spent a total of 3 hours in class), and somewhere along the line, it has a few examples of proving that certain types of computing machines are Turing-complete. (And it gives a definition of a Turing machine.)
Reputation Points: 1135
Solved Threads: 173
Super Senior Demiposter
Offline 2,479 posts
since Jun 2005
Unsolved 
