1 Replies - 1038 Views - Last Post: 17 July 2012 - 10:13 AM

#1 JTHM  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 25-April 12

Emulating Multiple Turing Machines

Posted 17 July 2012 - 09:35 AM

Hello denizens of Dream.In.Code, I'm looking for a proof of something pretty basic (just for curiosity, not schoolwork), but I can't quite figure out how to prove it.

I know that for a universal Turing machine to emulate the operation of another Turing machine on input w takes time at least proportional to the number of steps that the emulated Turing machine would take to halt on input w.

What I believe is true, but cannot think of a way to prove, is that emulating multiple Turing machines on input w, and returning an integer stating how many of those machines accepted on w, must take time at least proportional to the time it takes the first TM to halt on w + the time it takes the second TM to halt on w + the time it takes the second TM to halt on w, etc, all the way down to the last TM.

Can anyone demonstrate that this must be the case or point me to a good book or website that has the answer?

Is This A Good Question/Topic? 0
  • +

Replies To: Emulating Multiple Turing Machines

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7578
  • View blog
  • Posts: 12,740
  • Joined: 19-March 11

Re: Emulating Multiple Turing Machines

Posted 17 July 2012 - 10:13 AM

Assuming a single thread. I think it's not hard to see how this is proved. In order to execute the task as described, you have to execute the task serially for TM1, TM2, TM3 ... TMn, meaning the time to complete the task is the total of the time taken by the subtasks. Since there is no shortcut (see halting problem) no matter how you rearrange the tasks, this is a lower bound.

Actual time taken could be reduced by adding multiple processors, but that's not an interesting direction for the problem.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1