(I’ll try to keep everything here as simple as it can be. I may oversimplify some things. Consult with this for more precise results.)

So a while ago I stumbled across a paper (link above) which contained proof that problems solvable by certain type of hidden information machine with space limit of n contain set of problems solvable in time \(2^{2^{…^{2^n}}}\) on deterministic machine, with height of stack predetermined by exact type of machine (number of "players"). Using time hierarchy theorem, closure of sub-k-EXP functions under taking squares and existence of k-EXPTIME complete problems (trivial example – given description of machine and n in unary does machine halt in \(2^{2^{…^{2^n}}}\) steps with k 2’s in stack?) we can conclude that k-EXPTIME contains problems requiring \(2^{2^{…^{2^n}}}\) steps, thus from these hidden information machines we can find very intractable problems! Furthermore, certain machines are undecidable even under constant space constraint!


I’ll define these machines in terms of multiplayer games, as for me it is simpler. We have \(k>0\) players, numbered 0 to k-1. Players are divided into 2 teams - ∀-team consisting of ∀-players and ∃-team consisting of ∃-players. There is no big importance in number of ∀-players, so we can assume there is only one such player, numbered 0. In game there is finite number of memory banks (tapes for machines, but in game interpretation it can be whatever). Each player can see some subset (not necessarily proper) of memory banks, and has possibility to change content of some subset of it. These subsets are predefined before start of game. This type of game is called private game and is denoted MPA-k, where k is number of ∃-players.

Very important fact is that this game is non-cooperative. Of course, ∀-team is against ∃-team, so no cooperation is possible, but we don’t allow any two or more ∃-players be allies, i.e. they can’t have “group strategy”, which they agreed on before game. Only way of communication is through a memory bank visible to both players.

If we add restriction that every bank modifiable by ∀-player is invisible for ∃-team, ∃-players will have to play “blind”, without knowledge on what ∀-player is doing. This type of game is called blindfold game and is denoted MBA-k, where k is number of ∃-players.

But it can be easily shown that even MPA-2 with memory banks restricted to constant size have undecidable outcome, which I’ll show later. We can restrict these games by making hierarchy: if player n can see some memory bank X, so can any player m with \(0<m<n\). With this constraint space bounded games will be equivalent to some multiexponential function of space bound. Surprisingly, time bounded machines of each type have same outcome class!

MPA-k>1 outcome is fairly hard

With fairly hard I meant very hard. So hard that Turing machine can’t predict it. Suppose we have some TM halting problem instance written in place visible for everyone. We have 3 players - ∀-player and 2 ∃-players. ∃-players don’t have any memory bank visible for both of them other than input, and each of them has register he can use to send information to ∀-player. Also, ∀-player has his own private register. ∃-players try to win in finite time in following game – let #C0#C1#...#Cm# denote configuration history of Turing machine in question, where C0 is input and Cm is accepting configuration. ∀-player chooses players alternatingly and asks them for one symbol of configuration history. During this he checks 3 things:

  1. Is C0 input configuration?
  2. Is Cm accepting configuration?
  3. Do both players give same sequences?

It’s easy to see it can be checked in constant space. After that he asks player 1 to repeat history and player 2 to do the same, but starting from C1 instead of C0. ∀-player checks if Ci given by player 2 is really next step after C(i-1) given by player 1. This can also be done in constant space (Note that if players could exchange information they could lie, e.g. they now could give different histories, as long as C(i-1) of first of them evolves to Ci of other one. These histories don't have to be themself valid). If at any step either player was mistaken, ∀-player wins. Otherwise, if ∀-player finds no flaw and game ended, ∃-team won.

So ∃-team can win this game iff it can give configuration history leading to halt, which, of course, is possible only if machine in question halts. So outcome of constant space MPA-2 game is undecidable. Obviously, by adding other players idle during whole game doesn’t make result false.

Hierarchial games are equivalent multiexponential time DTMs

Strategy counter game

(Possibly tomorrow)