So I've been working on a problem for fun and I'm worried I've run into some sort of contradiction, so I'm trying to figure out where I went wrong. I've simplified the issue down to this:

Decider acceptance can be reduced to LBA acceptance

Part 1: A decider can be reduced to a decider with an empty input alphabet.

  1. Let $D$ be a decider with input alphabet $\Sigma$ and $\omega$ be an input string in $\Sigma^*$

  2. Construct a decider $D_0$ with an empty input alphabet and the same tape alphabet as $D$, which starts by writing the characters of $\omega$ to the tape, returns to the left side, and then executes identically to $D$

  3. $D_0$ accepts the empty string $\epsilon$ iff $D$ accepts $\omega$

Part 2: A decider with an empty input alphabet can be reduced to an LBA

  1. Let $D_0$ be a decider with an empty input alphabet

  2. $D_0$ halts in finite time, and therefore uses finite portion of the tape of size $m$

  3. Construct an LBA $A$ with the same states, symbols, and transitions as $D_0$ where the length of the tape is given by linear function $f(x)=x+m$

  4. The only possible input is $\epsilon$, so the size of the tape will be $m$, so $A$ will execute identically to $D_0$ and not go out of bounds

  5. $A$ accepts $\epsilon$ iff $D_0$ accepts $\epsilon$

This seems to prove that a decider can be reduced to an LBA, which is well known to be incorrect. I have a couple of guesses for where the error might be:

  • It could be in part 1, if you can't call a machine without input as powerful as a machine with input. After all, the only languages $D_0$ could accept are $\emptyset$ and $\{\epsilon\}$, which are both regular, not recursive. So you can't say that an input-less decider accepts the same set of languages as a decider, but maybe it's as "powerful" in a more abstract sense?

  • It could be in part 2, with the main problem being that computing $m$ would require running the decider, so the reduction to the LBA would be just as difficult as the acceptance problem. In other words, does the information you have prior to running automata change how powerful you can consider the automata to be?

Basically, I'm wondering if either of these concerns is the actual issue or if it's something else. And if either of these concerns isn't actually an issue, could you explain why? Thanks!

Edit: As pointed out, I should've represented these as decision problems, so part 1 would be a reduction from $\{(D,\omega) | D\textrm{ is a decider that accepts } \omega\}$ to $\{D_0 | D_0 \textrm{ is an inputless decider that accepts}\}$ and part 2 a reduction to $\{A | A\textrm{ is an inputless LBA that accepts}\}$. I believe the first two of these problems are recursive and the third is context-sensitive, so the first reduction is possible but the second isn't, due to $m$ not being computed.

  • 2
    $\begingroup$ You won't be able to compute $m$. $\endgroup$ Dec 24 '20 at 7:59
  • $\begingroup$ If the input alphabet is empty then nothing at all can be written onto a tape, since there are no symbols that one could write. My best interpretation is that you mean "empty input" instead of "empty input alphabet". $\endgroup$ Sep 20 at 18:16

You seem to be mixing some concepts. Over an empty input alphabet, there are no decision problems, so as a model, Turing machines with empty input alphabets are not interesting.

It is true that the problem of deciding whether a given TM accepts the empty word is interesting (and undecidable), but it's not the same thing as having an empty input alphabet.

So the "reductions" you describe are not exactly reductions in the formal sense, just some translations between models.

As for a concrete problem with your argument: first, an LBA runs on a fixed portion of the tape which is prescribed by the input length. If you have an empty input, the LBA is not allowed to touch the tape, so it can't really do anything. An LBA doesn't just mean that the space is linear in the input. So you can't manually add the "m" input cells. This breaks your argument.

But also note that the definition of the function $f(x)=x+m$ is a bit strange, since on an empty input alphabet, you always have $x=0$.

  • $\begingroup$ You're right, I should've represented them as decision problems, I added an edit to do that and I think I now see where I went wrong. I don't think you're right about LBA's though; I think you can add a constant amount of space to the tape without breaking the definition of an LBA - I'm not positive though. $\endgroup$
    – yosho27
    Dec 24 '20 at 15:50
  • 1
    $\begingroup$ Your formulation as decision problems is inaccurate, since it doesn't assume the given input is a decider. As it's now, everything will be undecidable since you can't detect whether a TM is a decider. You should formulate it as a promise problem. $\endgroup$
    – Shaull
    Dec 24 '20 at 20:28

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.