Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
