A /blackout machine/ is a Turing machine where every transition rule
prints a 1 to the tape. Is it decidable whether a blackout machine
will halt when given [arbitrary string, say empty string or singleton
string 1] as input?

My answer: yes, in time polynomial in Q, the number of states of the
machine.

Lemma: A blackout machine's tape will always consist of a single
contiguous string of ones. The tape head will always be either on the
string of ones (the 1nterior), or on the blank cell immediately left
or right of the interior (the left and right frontier).

Lemma: If the tape head is in the interior, you can decide in
polynomial time whether it will stay in the interior forever.

Pf: Simulate for Q steps. If the tape head has not exited, the finite
control has entered a cycle. For as long as it reads a 1 on the tape,
the same cycle of transitions will continue. Consider the net
displacement of the tape head during one cycle. If the net
displacement is zero, the tape head will remain in the interior
forever (the machine will never halt). Otherwise, it will eventually
reach one frontier or the other.


Lemma: If the tape head enters the interior, you can decide in
polynomial time whether it will exit on the left or right frontier (or
loop forever in the interior).

Pf: Starting from the step just after you transition to the interior
(so all transitions read 1 on the tape head), simulate for Q steps. If
we haven't exited by then, we must (as before) have a cycle of
transitions. The sign of the cycle's net displacement tells on which
frontier it will exit.

(Note that weird zigzag cases, such as the tape head zooming left into
the interior, zooming right for a considerable ways, then zooming net
left, and somehow exiting on the right are precluded. They are
precluded because the cycle is assumed not to exit the interior in the
first round.)


Lemma: If the tape head enters the interior, you can decide in
polynomial time on which frontier it will exit (if any), and what
state the machine will be in when it exits. Furthermore, the decision
depends only on the state of the machine upon entering, the side
entered, and the number of ones (mod 2Q?).

Pf: The cycle begins at some physical tape location. Imagine that each
time you re-enter the interior, you annotate the tape cells with the
state of the machine the first time you enter that tape cell anew. I
assume that the sequence you write /must/ be a repeating pattern that
has something to do with the cycle of transitions (e.g. must be
shorter than?). The pattern itself is dictated by the state of the
machine upon entering and the side entered. The state upon exiting
depends on the aforementioned pattern and the number of ones (because
the number of ones dictates which index in the repeated pattern will
be the last one).

Observation: Staying in the interior maintains the number of ones on
the tape. Exiting the interior maintains the number of ones on the
tape (depending on whether your model prints before or after
transitioning). Transitioning from a blank cell increments the number
of ones on the tape; this happens whenever entering the interior or
"exploring the exterior" (transitioning from a blank cell to a blank
cell).

Observation: There are four important types of transition:
- Interior transition, where you read 1, transitioning to a cell
  containing 1.
- Exterior exploration, where you read 0, transitioning to a cell
  containing 0.
- Enter the interior, where you read 0, transitioning to a cell
  containing 1.
- Exit the interior, where you read 1, transitioning to a cell
  containing 0.

Lemma: If you enter and exit the interior Q times in a row on the same
side, the machine loops forever.

Pf: There are Q transition rules of the form "If you read blank space
when in state q, write 1 to the tape and shift." (one rule per state
q).  [....]

Thought: possibility of taking a really long time, zigzagging
irregularly between frontiers?

Thought: When deciding what state the machine will be in, the result
depends on the number of ones. There's a repeating subpattern of
"state when visiting this tape cell for the first time" whose length
is no longer than Q, but which may be shorter. Also there's
potentially introductory prefix of states before the cycle is
entered. That prefix has length at most Q. So to really determine the
state upon exiting, it seems you potentially need to know the number
of ones minus the prefix length, all mod the repeating strand length.


Thought: Consider the state the machine is in when it first enters the
interior (the current cell reads a 1). There are Q possible choices of
state.  Imagine a machine that annotates a tape with the state the
blackout machine would be in the first time it entered that interior
cell assuming all previous transitions have been in the interior as
well. The sequence of states would either be finite (if the machine
would eventually loop, or always quickly exits the interior), or
infinite in one direction only. (It can only be infinite in one
direction. After at most Q steps in the interior, the machine enters a
cycle. The net displacement during that cycle dictates the infinite
direction.)

So for each direction of entering the interior, and for each state you
might be in upon entering the interior, we have a tape pattern. That
pattern consists of a fixed prefix of length at most Q, and a
repeating pattern of length at most Q.

Hence we have 2 (directions) x Q (states) patterns, where each pattern
has a prefix of at most Q (prefix) symbols and a repeating unit of
length at most Q symbols.  

We can create 2Q deterministic transition graphs representing these
patterns (representing "after entering the interior of k ones from
this side, on what frontier do I exit and in what state?"). Each graph
has at most 2Q states, and the number of ones dictates the current
state, and incrementing the number of ones increments the current
state. (So after Q increments, all graphs are in their loop part.)

Thought: Ok, so suppose you know for each state whether when the tape
head is on the frontier and the machine is in that state, whether the
next transition will explore or enter the interior (and if so,
whether/where/how it will exit). How do you detect looping?

Well, we've said that if the interior is bigger than Q, the eventual
exit state depends at most on the size of the interior, mod each
integer 1..Q.

I count three ways to loop:
1. Looping in the interior, detectable when you have a cycle with zero
   net distance. 
2. Looping on one frontier, detectable when you enter and exit on the
   same side Q times in a row. Helpfully, entering and exiting on the
   same side can probably take no more than like 3Q steps each time.
3. Looping on frontiers, detectable with difficulty. If you keep track
   of what N is mod 1...Q, what side of the frontier you're on,