Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 30 October 2013, 17:00 hrs

Room: S17#04-06, Department of Mathematics, NUS

Speaker: Yang Yue

Title: A real Turing machine

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract

It is well-accepted that Turing program formalizes the concept

“algorithm”, as long as the domain is N. However working

mathematicians deal with algorithm over R all the time. So the

question for recursion theorists is: Are there “natural” computation

models for real numbers? Naturalness here should at least include the

following features: It should agree with the intuition of working

mathematicians; the theory should be developed within arithmetic, at

least not involving large cardinals nor determinacy; when restricted

to natural numbers it should coincide with the standard Turing

machine; it should be further generalized to computation on higher

types; the computation should have steps which may or may not be a

natural number, thus potentially lead to complexity theory;

computation should be essentially finitary and discrete; relative

computability can be defined on top of it, thus potentially lead to

degree theory. No, this is not a philosophy talk.