# Where is the problem in this proof that deciders are no stronger than LBAs?

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.

• You won't be able to compute $m$. Dec 24 '20 at 7:59
• 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". Sep 20 at 18:16

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$$.