A game-semantic model of computation

DOI10.1007/S40687-018-0163-ZMaRDI QIDQ2319854zbMATH OpenOpenAlexFDO

Publication date 20 August 2019

Published in Research in the Mathematical Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1702.05073

Semantics in the theory of computing (68Q55) Turing machines and related notions (03D10) Abstract and axiomatic computability and recursion theory (03D75)

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 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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: A game-semantic model of computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2319854)