# If a DFA can be simulated by a real program, can it be simulated by a TM

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.

-
Yes, of course. –  Karolis Juodelė Mar 29 at 20:10

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.

-
Typical programming languages are Turing complete and thus are equivalent in power to TMs. Also, distributed computing can be simulated by TMs - A single TM can simulate arbitrarily many other Turing machines (= communication partners) at the same time. It sure gets much slower, but it works. And assuming that a human is also just a computation machine that is Turing complete, even user interaction could be simulated by a TM. That last assumption is of course debatable. –  Jost Mar 29 at 21:40
@Jost: A TM like you describe can simulate serialisations of parallel computations, but not the parallelism. For instance, notions of runtime and communication overhead get muddled. Another thing that TMs don't model are streaming/online algorithms, e.g. operating systems. Adding that. –  Raphael Mar 30 at 11:34

The Church–Turing thesis states that every intuitive model of computation can be simulated by a Turing machine. This is not a theorem, just an informal principle, which holds in your case: every C program can be simulated by a Turing machine. Formally showing this would be tedious, but such facts are commonly assumed.

The fact that C is Turing-complete is in fact stronger than what you need: it states that C can be simulated by Turing machines and vice versa.

-
I thought the "vice versa" part was implied by something being Turing-equivalent, not Turing-complete. en.wikipedia.org/wiki/Turing_completeness#Formal_definitions –  AmadeusDrZaius Mar 29 at 21:06