0

I am writing a proof for a problem, and in that proof, I am simulating a TM M that has k states and terminates after being started on a blank input. I want to show that to simulate M on a TM M', M' would have f(k) number of states, where f is a computable function.

Is it simply sufficient to state that simulating M with k states would require more than k states, and that since M eventually terminates, this number of states is finite and can be written as a function f(k)?

This seems self evident, but I am not sure if I need to be more formal than that.

Jay Hu
  • 1
  • What does it mean to "simulate" a Turing machine? (Consider the case where the machine being simulated has a billion-state description, but only three of those states are ever actually used . . .) – Noah Schweber Apr 15 '16 at 21:52
  • You can always get away with a fixed number of states, due to Turing's famous theorem that there exists a universal Turing machine: https://en.wikipedia.org/wiki/Universal_Turing_machine – Lukas Geyer Apr 15 '16 at 23:51

0 Answers0