1
$\begingroup$

I have always read that Turing machines can simulate any algorithm, without changing the time complexity of the algorithm, and hence it is easier to study the Turing machine equivalent of the algorithm while doing proofs.

However, I am unable to find a proof for this statement. Is there a formal proof of why the Turing Machine model should be able to simulate any algorithm within the same time complexity?

$\endgroup$
2
$\begingroup$

This is not a formal statement, but either a definition or an empirical observation. The full claim is something like the following:

"A reasonable model of computation (for discrete data) together with a reasonable notion of time complexity will have the property that it can be simulated by a Turing machine with at most polynomial increase in time complexity."

The two occurances of "reasonable" here are generally not seen as formal notions, but rather as informal notions. We can trivially define models of computation with notions of time complexity not having the property above, but these models do appear artificial. On the other hand, models people actually want to use have the property.

Any attempt to formally define what a "reasonable model of computation with time complexity" is would probably include the possibility of polytime-simulation by a TM as an axiom.

$\endgroup$
  • $\begingroup$ What you're referring to is called the Extended Church-Turing Thesis. Quantum computing is typically viewed as a potential (empirical) counter-example to the ECT thesis. It depends on whether BPP = BQP. At this point in time, it would be a bit silly to define "reasonable model of computation" in such a way as to (seemingly) exclude quantum computing. $\endgroup$ – Derek Elkins Nov 3 '18 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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