0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ You don't need to worry about how K might work. You need to think about what you could do if you had such a K. $\endgroup$
    – Derek Elkins left SE
    Jun 23, 2019 at 21:01
  • $\begingroup$ That's why my idea to check if specific Turing Machine is contained in "terminates on empty word" set is invalid, right? $\endgroup$
    – Andy
    Jun 23, 2019 at 21:07

1 Answer 1

Reset to default
2
$\begingroup$

Is that proof correct?

Let's assume f is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size.

This TM works as following:

  1. Using blackbox for f, calculate f(n)
  2. Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {_, 0, 1, .... n}
  3. Simulate each machine on empty input BUT we don't check TM machine one by one. We check TMs STEP BY STEP. That means for each TM we make its one step.
  4. When TM terminates, add 1 to counter
  5. When counter reaches f(n), then we know which machines terminates and which don't. We have solved halting problem. Contradiction

The key is we don't simulate TM machines one by one, but step by step, thus we don't get looped and we always terminate.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Yes, this works. One minor concern that doesn't come up in this case but is worth mentioning is how we interleave the execution of the TMs. In this case, because there are only a finite number of relevant TMs, we can just iterate through them incrementing each in turn. When we're dealing with an infinite number of TMs, though, we use a technique called dovetailing since if we just took a single step from each TM before taking the second step, we'd never get to the second step of any. Again, this isn't an issue in this case. $\endgroup$
    – Derek Elkins left SE
    Jun 24, 2019 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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