On Turing machines with syntactic restrictions
by Dr. Keisuke Nakano
- When: Friday, 22/10/2021, between 9am and 10am EDT (1pm-2pm UTC)
- Where: Zoom; Outside guests please RSVP by emailing Harley Eades
- YouTube Stream/Recording: https://youtu.be/lCJ2Kq4heTI
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.