We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A game-semantic model of computation.
- Authors
Yamada, Norihiro
- Abstract
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, 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 toward a new mathematical foundation of computation, intuitionistic logic and constructive mathematics.
- Subjects
SEMANTICS; COMPUTABILITY logic; COMPUTABLE functions; MATHEMATICAL logic; MATHEMATICS
- Publication
Research in the Mathematical Sciences, 2018, Vol 6, Issue 1, p1
- ISSN
2522-0144
- Publication type
Article
- DOI
10.1007/s40687-018-0163-z