The Conway Machine: A Game-Valued Model of Computation

We define the Conway Machine (CM): a finite-control computational model whose tape cells hold combinatorial games and whose primitive transitions branch on Conway’s four-valued outcome classifier o : G → {L, R, =, ∥}. We distinguish three cost regimes for the classifier — oracle (CMo), full-computation (CM∗), and P-feasible (CM♯) — and adopt the last as theworking convention. We establish four formal results. First, on the numeric regime No<ω , CM♯ is polynomial-time equivalent to deterministic Turing machines. Second, the outcome classifier is not a monoid homomorphism under disjunctive sum, witnessed by ↑ +∗ ∥ 0 while 1+∗ > 0. Third, under succinct encoding, deciding o is PSPACE-complete on short games and EXPTIME-complete on stopper-sided loopy games with finite position graph. Fourth, under oracle semantics CMo, the induced CM complexity classes coincide with P, PSPACE, and EXPTIME on the corresponding regimes (Corollary 8.8), with strict outer separation by the time hierarchy theorem. We introduce a two-axis parameter space (S, α) with S ranging over game regimes (Numeric ⊂ Short ⊂ Loopy ⊂ Transfinite) and α an ordinal time budget, and locate eight classical computational paradigms (TM, BSS, ITTM, OTM, ordinal registers, surreal BSS, Wegner interaction machines, Burgin inductive TMs) as heuristic cells.