The one bit computer scientist thought experiment

Question

This is a thought experiment that has been noodeling around in my head for a while but I'm yet to come up with a good answer to it.

Suppose a philosopher angry at almost staving due to a deadlock has imprisoned a computer scientist in a room with a programmable Turing equivalent machine, a clock and a light bulb affixed to the wall (along with the basic necessities of life).

When programmed the machine will act as a function $\mathbb{N} \to \{0,1\}$. Each day at noon the light will either be switched on or remain off. If the computer scientist correctly guesses if the light will be switched on then they are rewarded with copies of interesting papers however if they guess incorrectly they are punished by being forced to grade first year undergraduate essays.

The computer scientist knows that the light's sequence has been created by a Turing machine exactly like there own running a single non changing program that the scientist does not know.

What is the best strategy to maximise the computer scientist's reward.

Answer 1

I interpret the problem to be:

• The philosopher has some Turing machine implementing some function $f: \mathbb{N} \to \{0,1\}$

• The scientist tries to guess $f(n)$ on day $n$. They can use past observations $f(1), f(2), ..., f(n-1)$ if desired. To help them guess, they are welcome to use a Turing machine (or not, i.e. just use pure thinking).

• The two Turing machines do not necessarily have anything in common like state space, alphabets, etc.

• The specification that the philosopher has a Turing machine simply means $f$ must be computable.

• The specification that the scientist has a Turing machine simply means they don't have some other oracle.

First of all, is my interpretation correct?

IMHO if you can't make any assumptions about the distribution of the philosopher's choice of $f$, there is nothing you can do. For every Turing machine $M$ that outputs a specific sequence the first $n-1$ days and then $0$ on the $n$th day, there is another machine $M'$ that outputs the same sequence followed by $1$ on the $n$th day, and vice versa -- simply add the equivalent of an IF statement.

If not for the halting problem (haha!) then a good approach would have been: always guess that the philosopher is using the "smallest" Turing machine possible that fits the observed sequence. ("Small" is defined as being listed early in a list of all the countably infinite machines.) If only you could solve the halting problem (i.e. by having such an oracle), this would have worked because after some finite no. of days you would have the correct machine and can enjoy success forever after.

---

In reality the following might be worth trying...? Replace "the smallest Turing machine" idea with the "most compressible sequence". I.e. guess whichever one of $(f(1),...,f(n-1), 0)$ or $(f(1),...,f(n-1),1)$ is "more compressible". Now of course, there are lots of theoretical problems with the notion of "more compressible" -- i.e. compression by what class of machine/oracle/description? But instead of going "high-tech" like that, we can go "low-tech" and just compress by Ziv-Lempel, or even Huffman code, and hope for the best. :)

Answer 2

Since this is SE/Math, I guess we should start with a more formal definition of a Turing Machine.

With the model and vocabulary used there, we can clarify the idea of:

The computer scientist knows that the Light's sequence has been created by a Turing machine exactly like there own running a single non changing program.

as:

The Subject

• knows the $\langle Q, \Gamma, b, \Sigma, q_0, F\rangle$ of the machine $M$ which is driving the Light,
• always knows what day it is,
• knows how the day-number will be encoded into $M$'s initial contents when it is run each day,
• knows which of the (presumably two) final states $f\in F$ will trigger the Light to turn on,
• can model arbitrary Turing Machines in negligible time, or otherwise reason about Turing Machines in superhuman ways.

We assume the Subject doesn't know $\delta$ (the transition function) because if they did then they could just run the machine with each day's input the night before, and exactly predict the outcome.

We assume the Subject has unlimited ability to model Turing Machines because if they don't have unlimited ability, then we have to go looking for the best strategy within such-and-such ability limits.

So really, the Subject is trying to figure out (or guess) what $\delta$ is.
Delta is a function from the machine's current (non-halting) state and the current symbol under the reader-head, to the symbol it should write and the new state it should take internally and how the head should move. $$\delta:(Q\setminus F)\times\Gamma\to \Gamma\times Q\times\{L,R,N\}$$

Critically, because $Q$, $\Gamma$, and $\{L,R,N\}$ are all finite, there are finitely many functions $\delta$ could be.
This means the Subject can just start with a list of possible $\delta$, and every day cross off from that list any that wouldn't have resulted in the Light's behavior that day. After finitely many days, there will only be one remaining candidate, and the Subject will be able to predict the Light perfectly from then on.

[There's a catch! Not all of the candidate $\delta$s will give machines that actually do terminate. Determining if a given machine will ever terminate isn't covered by our assumption that the Subject has unlimited ability to simulate machines in "negligible time"! Either the Subject can make determinations about the behavior of machines in more powerful ways than just running them really really fast, or the Subject can simulate machines "infinitly quickly" (whatever that means), or the Subject can't simulate them in "negligible time". Since we already assumed they could do such simulations, let's assume one of those first two abilities as well.]

Of course "finitely many days" will probably be a very long time. What should the Subject be guessing in the mean time?

It's not clear that a "best strategy" is possible for these initial $x$ days. Unless the Subject knows something about the Philosopher or the Philosopher's capabilities, any prior probability distribution the Subject assigns to the candidate $\delta$s will be arbitrary. They could treat the remaining candidates as "votes" for that day's prediction, but this is just choosing a uniform distribution.
A uniform distribution is a reasonable choice, but maybe the Subject should assign higher probability to "simpler" "programs". How would they do that? How, other than observing this whole gedankenexperiment many times, could we say if their choice was a good one or not?

There are slightly different ways we could formalize your question, but I suspect they will only slightly change the answer.

Answer 3

If we assume that cryptography is possible at all, then the task is pretty hopeless.

The philosopher can easily have programmed his machine to implement a stream cipher that produces a sequence of pseudorandom bits to control the light with. If the cipher is secure, then even after observing the bits produced so far, it will be computationally infeasible for the computer scientist to guess the next bit with a success probability better than 50%.

The computer scientist should implement a stream cipher of his own and initialize it with a random key. That way he can at least expect to win half of the days -- no matter which program the other machine actually runs.

Answer 4

I've already linked to the needed formal definitions, but there are two other interpretations of your question that are worth looking at.

Basically, what if the Light's behavior is taken from Machine states during a single ongoing execution of the Machine.

In the first case, we could suppose that there's a mapping $Q\to \{on,off\}$, and the machine runs a predetermined number of steps ($s_n$) every day ($n$), after which it's paused and its state drives the Light.
For this purpose, we should assume that the machine has no halting condition.

In this situation I don't think it matters if the Subject knows $\delta$. If they don't, it just multiplies by some gargantuan (finite) factor the number of possibilities they need to be keeping track of.

Because there's no upper bound on the length of the initialization, the Subject might never be able to predict the Light with perfect confidence. But it's not impossible (or even improbable) that they will be able to, and in any case they can make some headway.

On day $n$ the head can have moved at most $\sum_{n'=1}^{n-1} s_{n'}$ steps from the starting point (in either direction), and it can move at most $s_n$ more steps away that day. Therefore on any finite day, the Subject will have finitely many possibilities to worry about, some of which can be eliminated when they fail to predict the Light that day. If every remaining candidate has gone into a loop, then the Subject can confidently predict the Light from then on.

In the second case, if we modify the Machine a little we could restart it after it halts on its own. Just redefine $\delta$ $$\delta:Q\times\Gamma\to \Gamma\times Q\times\{L,R,N\}$$ ($Q$ instead of $(Q\setminus F)$), and define a mapping $F\to \{on,off\}$ for the Light.

In this case I'm not sure the Subject can make meaningful progress. If they don't know anything about how the tape was initialized, then they can't make any assumptions on how far the head might travel each day, so there will always be countably infinitely many candidates not-yet-eliminated.

In both cases, Brian Borchers's comment on my other answer is relevant. The Philosopher can't pick an initialization uniformly at random without deciding on an upper bound for it's length. That said, if the Subject doesn't know anything about how the Philosopher actually does pick the initialization, then I don't know they should use this fact. $$\mathscr{M}\mathit{aybe\ that's\ the\ true\ heart\ of\ your\ question.}$$