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
