2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, of course. $\endgroup$ Mar 29, 2014 at 20:10

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jost
    Mar 29, 2014 at 21:40
  • $\begingroup$ @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. $\endgroup$
    – Raphael
    Mar 30, 2014 at 11:34
1
$\begingroup$

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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.