I'm having an issue determining whether certain languages are decidable,
recognizable or neither.
The specific languages I'm referring to are of the following form
L = {<M> | for every w, M accepts w after at most |w|/2 steps}
L = {<M> | for every w, M accetps w after at most X steps}
L = {<M> | for every w, M accepts w after at least X steps}
L = {<M> | there is no input which M terminates in fewer than X steps}
L = {<M> | M is a Turing machine and the number of states of M is prime}
Up till now all the languages I encountered were usually taking an input of the form <M,w> which made it easy cause it was always some sort of a manipulation that required running the Turing machine M on the input w in some form, but I have no idea how to even start thinking regarding these languages, any direction or hint as to how to approach these sort of questions will be very helpful !
Best Answer
Something is funny (interesting) about the first language. To be in the first language, the machine must accept every string $w$ in at most $|w|/2$ steps. One might at first suspect that language would be undecidable, but it turns out to be decidable for a somewhat trivial reason.
What if $w$ has length $1$? Then $|w|/2$ is $1/2$. Steps are measured with natural numbers, and the machine cannot do anything in $0$ steps, so let's be generous and say the machine must accept $w$ after one step. The only way this can be done is by re-writing the symbol under the head to "1" (that is, "accept") and transitioning to the halting state. Those actions together take one step.
For the machine to be in the first language, this has to happen for every $w$ of length $1$. In other words, for every symbol of the input alphabet, the machine must immediately write a $1$ on the tape and transition to the halting state. Indeed, the machine accepts every string of length $1$ in $1$ step if and only if the machine follows the previous sentence for every input of length $1$. And in that case, it accepts every string in $1$ step.
So we can decide whether a machine is in the first language: we only have to look at the state table for the machine and see whether it has all the transitions mentioned in the previous paragraph. That can be done by literally examining the code $\langle M \rangle$ for the machine.
A similar analysis will apply to the second language, as well: when the length of the input is much larger than $X$, the machine is unable to actually see then entire input in $X$ steps. So the machine accepts every string in $X$ or fewer steps if and only if it accepts every string of length $X+1$ in $X$ or fewer steps, because the behavior of the first $X$ steps is completely determined by the first $X$ symbols of the input. That is a finite number of strings that we need to test, so we can effectively determine whether a machine is in the second language.
Another similar analysis will apply to the fourth language. A machine halts on an input in fewer than $X$ steps if and only if the machine halts on the first $X+1$ symbols of the input in fewer than $X$ steps (because, when the machine halted in fewer than $X$ steps on the whole input, it never saw the $(X+1)$st symbol of the input). So a machine is in the fourth language if and only if there is no input of length $X+1$ for which the machine halts in fewer than $X$ steps. That is a decidable question; we only have to run the machine for $X$ steps on all inputs of length $X+1$ to answer it. So the fourth language is also decidable.