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.
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 Brainfuck. If you can write a Brainfuck 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/courses/modcomp/fall2006/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.)
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.