Let f: N → N be a function where
f(n) = number of Turing Machines over input alphabet {0, 1}, states: {0, 1, ..., n} and work alphabet {_ (blank), 0, 1, ... n} which terminates on a empty word
.Is
f
computable?
Let's call a TM which solves this problem K
.
It feels like this problem is uncomputable. If we can't even determine if particular TM halts on an empty word (Halting problem reducing to the blank tape halting problem), then intuitively finding number of TMs with this property should be even harder. But I can't think of any reduction since this problem doesn't utilize any particular TM in input, its input is just a number (in the question I linked above - BLANKHALT, TM takes a machine as an input so we can provide a specific machine - anything we want - for example machine from instance of the HALT problem, but this is not a case in this problem).
At first I wanted to reduce BLANKHALT problem: I wanted to measure its number of states, alphabet, run the K
TM with number of states BLANKHALT instance has and while counting the number of TMs which terminated on empty word, check if this is BLANKHALT machine I have just asked for. BUT I cannot do this, since I cannot assume K even enumerates the TMs, right? If K
existed, it might have a magical way to solve the question, without checking all possible TMs one-by-one, right?
K
might work. You need to think about what you could do if you had such aK
. $\endgroup$