[Solved]: If a DFA can be simulated by a real program, can it be simulated by a TM

Problem Detail: 

In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says that the $\mathsf{DFA}$ can be simulated by some $\mathsf{TM}$? Could a program be used in place of a $\mathsf{TM}$ in a proof of decidability?

I know that Java being Turing-complete would mean that it can simulate any $\mathsf{TM}$, so this is sort of the reverse of Turing-completeness I guess.

Asked By : AmadeusDrZaius

Answered By : Raphael

Assuming the same limited view on computation as Turing machines, then yes: typical programming languages are Turing complete and thus (for all we know) equivalent in power to TMs.

A simpler proof presents itself, too: if you look closely enough, finite automata are just Turing machines that don't use their tape.

Keep in mind, though, that Turing machines lack some features of modern real machines/languages: distributed computation (i.e. communication), user interaction, online algorithms and never terminating systems with continuous I/O (e.g. operating systems) are just some examples. If your simulation program uses such features, the simulation may not carry over to TMs.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23228

3.2K people like this

 Download Related Notes/Documents