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

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.

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.
• On your first point, Are you talking about the first step in the algorithm or how $n$ is represented? – Joe Man Analysis Apr 16 '19 at 6:54
• 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! – Joe Man Analysis Apr 17 '19 at 3:08