Menu
I found a Wikipedia article of a list of Turing machine equivalents. However, it doesn't tell a method of how to determine whether a given machine is Turing machine equivalent.
Do I need to use the definition of a Turing machine to prove it? Could you give an example?
Thanks.
514
What is Turing Equivalence? To say that a computational device is Turing equivalent means that it can do anything a Turing machine can. You typically prove Turing equivalence by showing how to implement a Turing machine interpreter on the device in question. Then you can use the device to simulate any Turing machine.
Markov algorithm is another remarkably simple computational model, based on string rewriting, equivalent to the Turing machines.
A Turing machine is the original idealized model of a computer, invented by Alan Turing in 1936. Turing machines are equivalent to modern electronic computers at a certain theoretical level, but differ in many details.
The standard way of proving something turing complete is to implement one of the TM-equivalents in your machine. If that is possible to do, then your machine is turing-complete. If it's not, then it's not. So if I was trying to prove, say, that a new programming language is turing complete, I'd pick the TM-equivalent that's simplest to implement, and then show that my programming language can simulate it.
68
Actually it cannot be really proven. At least, fully formalizing these common equality proofs might require much more formal logic than to be expected even in theoretical computer science. ( if you disagree, tell me! I am eager to discuss about this. )
However, it is mostly clear from context. You try build a simulation of a "machine" of scheme of computation A within another such model of computation B. This means B can simulate A, and hence has the full power of A. If you do vice versa, these two models are called equivalent.
1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
