Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable

Question

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.

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?