-1
$\begingroup$

Can we prove by induction that $A_k$ is computable for every choice of $k \in \mathbb{N}$?

$A_k$ is the set of descriptions of a no-input Turing Machine which accepts in $k$ or fewer steps.

$\endgroup$
1
0
$\begingroup$

Well, just simulate $M$ for $k$ steps and see if it accepts or not


Or, if you want to prove by induction for some reason (there shouldn't be any reason to do this), then just run the machine for one step and then use the induction hypothesis.

$\endgroup$
1
  • $\begingroup$ sorry, I forgot to specify. How to prove it by induction proof? $\endgroup$
    – justin
    Nov 3 '21 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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