Yang Yue: A real Turing machine

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.