Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Yes, of course. –  Karolis Juodelė Mar 29 at 20:10

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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
    
(And thank you for the answer. I've chosen Raphael's, but both of your answers were good.) –  AmadeusDrZaius Mar 29 at 21:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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