1
$\begingroup$

Let be $B$ a Busy Beaver function and set $W=\{\langle M \rangle :\text{$M$ stops in less than $B(10^{1000})$ steps on an empty tape}\}$. Is this set computable?


I'm not sure how to approach this question. I suspect that this set is computable and have tried to see if it is finite, but haven't reached anything.

$\endgroup$
  • $\begingroup$ I don't understand the definition of $W$. What is $M$? $\endgroup$ – Yuval Filmus Aug 21 '19 at 21:01
  • $\begingroup$ Hi @YuvalFilmus is a turing machine, thanks! $\endgroup$ – PCG Aug 21 '19 at 21:10
  • $\begingroup$ Let me phrase this differently. When does an integer $n$ belong to the set $W$? $\endgroup$ – Yuval Filmus Aug 21 '19 at 21:12
  • $\begingroup$ @YuvalFilmus when $n$ is a number of a turing machine (is a similar numeration of a Gödel numeration) and tha Turing machine with number $n$ stop with input the empty tape and stop in less $B(10^{1000})$ steps. $\endgroup$ – PCG Aug 21 '19 at 21:16
2
$\begingroup$

Your function is computable. Just run the input machine on the empty input for $B(10^{1000})$ steps. Note that $B(10^{1000})$ is just a constant which can be hardcoded into your code.

$\endgroup$

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.