2017/02/16 by Norihiro Yamada, Yamada, Norihiro
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1702.05073
openalex publication_date 2017/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The present paper introduces a novel notion of `(effective) computability', called viability, of strategies in game semantics in an intrinsic (i.e., without recourse to the standard Church-Turing computability), non-inductive and non-axiomatic manner, and shows, as a main technical achievement, that viable strategies are Turing complete. Consequently, we have given a mathematical foundation of computation in the same sense as Turing machines but beyond computation on natural numbers, e.g., higher-order computation, in a more abstract fashion. As immediate corollaries, some of the well-known theorems in computability theory such as the smn-theorem and the first recursion theorem are generalized. Notably, our game-semantic framework distinguishes `high-level' computational processes that operate directly on mathematical objects such as natural numbers (not on their symbolic representations) and their `symbolic implementations' that define their `computability', which sheds new light on the very concept of computation. This work is intended to be a stepping stone towards a new mathematical foundation of computation, intuitionistic logic and constructive mathematics.