On Turing machines with syntactic restrictions

by Dr. Keisuke Nakano

Abstract

A Turing machine is a computational model that can represent all computable functions. By imposing syntactic restrictions on the Turing machine, it is possible to construct a computational model that defines only computable functions satisfying a certain property P. However, it is not obvious whether the restricted computational model covers all computable functions satisfying the property P. In this talk, I will introduce computational models corresponding to the three properties of functions: injectivity, involutoriness, and idempotence. Although all of these properties are undecidable, the corresponding computational models are given as Turing machines with decidable syntactic restrictions.