Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps.

My Thoughts:

I am new to proving results like these with Turing machines, so I'm often not sure what is "legal" or "not legal" with a Turing machine. For example, my textbook often gives "high level" descriptions of Turing machines doing a computation instead of formally step by step. This is the way we are expected to describe Turing machines in class, but it often leaves me unsure if I'm being rigorous enough in my description.

My Attempt:

Construct a Turing machine $M'$ the following way:

$M'$ = "On input $\langle M,w,n \rangle$:

(1) Represent $n$ on the tape by $n$ consecutive $1$'s

(2) Simulate $M$ on $w$

(3) Each "execution" of the transition function is followed by a mark on one of the $1$'s

(4) If $M$ enters an accepting state, accept; Otherwise, reject if $M$ enters a rejecting state or after all of the $1$'s are marked."

My main concern is step (1) of the algorithm. I'm really unsure if that can be done. I'm also not sure how $n$ is represented as a string for the input $\langle M,w,n \rangle$. Am I able to choose how it's encoded?

Thank you for your time and feedback.


1 Answer 1

  1. This is not a problem. You have an infinite tape, so you can store whatever you want on it.

  2. Depending on how explicit your proof should be, consider a few edge cases for defining your transition function:

    a.) How does your TM recognize, if all n 1s are gone? The complexity of this depends on the alphabet of the TM, if $|\Sigma| > 2$ it should be easy, else you have to work out a few details.

    b.) After you've marked one of the 1s - how do you get back to the next step of your computation?

  • $\begingroup$ On your first point, Are you talking about the first step in the algorithm or how $n$ is represented? $\endgroup$ Apr 16, 2019 at 6:54
  • $\begingroup$ How n is represented. I thought that your concern was about the amount of available storage. $\endgroup$
    – oerpli
    Apr 16, 2019 at 10:45
  • $\begingroup$ My main concern was if I was allowed to represent/encode $n$ the way I did. Anyway, I believe I've solved the problem. Thank you for your feedback! $\endgroup$ Apr 17, 2019 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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