5
$\begingroup$

My professor discussed the following Turing machine M' on input (,x):

  1. Generate number n
  2. Run M on X, for n steps
  3. If M stops, accept

I don't understand No.3

If we are running M on input X for final number of steps then there is no way for M not to stop... so why he wrote if M stops?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You are running M', which simulates the TM M. So after n steps of the simulation M need not be in a stopped state. $\endgroup$
    – Bakuriu
    Dec 9, 2021 at 11:48
  • 1
    $\begingroup$ M might not have stopped in n steps. $\endgroup$
    – Polygnome
    Dec 9, 2021 at 12:25
  • 2
    $\begingroup$ Step 2 is an informal way of saying "Run M on X, and examine the state after n steps". $\endgroup$
    – chepner
    Dec 9, 2021 at 21:29
  • $\begingroup$ It's a shorthand for "if M stopped because it reached a final state in the given time, do X. Otherwise, if it was forcibly stopped by the time running out, do Y". Here X=accept, Y=do nothing. $\endgroup$
    – chi
    Dec 10, 2021 at 14:33

3 Answers 3

Reset to default
20
$\begingroup$

Step 3 could be phrased more properly as "If M has already stopped by the time we get to N steps, accept". Does that help to clarify?

Improve this answer
$\endgroup$
3
  • $\begingroup$ Still I don't get it... sure it will stop... what do you mean by not already stopped? $\endgroup$
    – Dan
    Dec 10, 2021 at 21:41
  • $\begingroup$ Okay, think of it like a computer instead. Start a program on your computer, and let it run for 30 seconds. Now, if the program has already stopped on its own, enter the accepting state. Otherwise, you had to kill the program yourself, so enter the rejecting state. $\endgroup$
    – Christian
    Dec 10, 2021 at 22:58
  • $\begingroup$ @Dan If it hasn't entered a final state before N steps, then it didn't stop, we just gave up waiting for it to stop. A Turing machine halts when it enters a final state. $\endgroup$
    – user253751
    Dec 11, 2021 at 17:49
5
$\begingroup$

Its an informal phrasing. I think it's easiest to stay with informal wording and just use more words to clarifiy.

M' cannot "run M for n steps, in the most literal of notation. You instead run another Turing machine, which I will call Mi, where the "i" means "insturmented." This new Turing machine has a few properties

  • Its input tape is initially filled with a counter (initially set to n) followed by X.
  • It provably decrements this counter towards zero. After some number of decrements occur, the state of the tape is identical to the state that M leaves the tape in after n steps (this is what they mean by "simulating." It's not the same machine, but it yields the same results)
  • It halts when the counter hits 0, or when it is done simulating a step of M that would cause M to halt.

It is actually reasonably trivial to construct such a machine. It is typically much slower than M, but Turing completeness is not concerned with that.

So what M' does is actually write n to the tape, followed by X. It then executes Mi, which, when it completes, either leaves a zero or a non-zero value in the counter. M' then uses that value to determine whether the simulated M halted, or if Mi had to cut it off beacuse it had run the specified number of steps.

This is, of course, one implementation. It doesn't have to be exactly that structure. But this is one structure which can be used to construct the proof your professor is using.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Another implementation would be to modify a universal Turing machine to count the number of steps, then use the modified UTM to simulate the TM you are interested in. $\endgroup$
    – user253751
    Dec 11, 2021 at 17:50
1
$\begingroup$

Revisiting the formal definition of a turing machine: https://en.wikipedia.org/wiki/Turing_machine#Formal_definition Here you have a set of 'final states' or 'accepting states'. These states do not have transitions to other states, so once the TM reaches an accepting state it can consider "stopped". I believe 3 is asking whether the simulated TM has reached an accepting state after N steps.

Improve this answer
$\endgroup$

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.