0

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.

2
Contributors
1
Reply
2
Views
10 Years
Discussion Span
Last Post by Rashakil Fol
0

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.