  In the previous work, we have given a novel, game-semantic model of
computation in an intrinsic, non-inductive and non-axiomatic manner, which is
similar to Turing machines but beyond computation on natural numbers, e.g.,
higher-order computation. As the main theorem of the work, it has been shown
that the game-semantic model may execute all the computation of the programming
language PCF. The present paper revisits this result from an automata-theoretic
perspective: It shows that deterministic non-erasing pushdown automata whose
input tape is equipped with simple directed edges between cells can implement
all the game-semantic PCF-computation, where the edges rather restrict the
cells of the tape which the automata may read off. This is a mathematically
highly-surprising phenomenon because it is well-known that the more powerful
non-deterministic erasing pushdown automata are strictly weaker than Turing
machines (in the Chomsky hierarchy), let alone than PCF.

Logic in Computer Science;Logic