Computing beyond Constructibility: The Recognizability Strength of Ordinal Time Machines

Duration: 57 mins 43 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/2141210/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Carl, M (Universität Konstanz) Wednesday 16th December 2015 - 13:30 to 14:30


Created:	2015-12-21 16:59
Collection:	Mathematical, Foundational and Computational Aspects of the Higher Infinite
Publisher:	Isaac Newton Institute
Copyright:	Carl, M
Language:	eng (English)


Abstract:	Co-author: Philipp Schlicht (Universität Bonn) Transfinite machine models of computation provide an approach to an `effective mathematics of the uncountable'. However, their set-theoretical interest seems to be limited by the fact that even the strongest such model, Koepke's Ordinal Turing Machines with parameters (pOTMs), can only compute constructible sets. Recognizability is a more liberal notion than computability in that it only requires the machine to be able to identify a certain object when it is given to it as an input, not to produce that object. By invoking notions from algorithmic randomness and considering recognizability rather than computability, we connect transfinite computability to large cardinals and forcing axioms incompatible with the axiom of constructibility on the one hand and inner models for large cardinals on the other. In particular, under appropriate large cardinal assumptions, a real number is heriditarily recognizable by a pOTM if and only if it is an element of the mouse for one Woodin cardinal. This is joint work with Philipp Schlicht.

Abstract:

Co-author: Philipp Schlicht (Universität Bonn)

Transfinite machine models of computation provide an approach to an `effective mathematics of the uncountable'. However, their set-theoretical interest seems to be limited by the fact that even the strongest such model, Koepke's Ordinal Turing Machines with parameters (pOTMs), can only compute constructible sets.

Recognizability is a more liberal notion than computability in that it only requires the machine to be able to identify a certain object when it is given to it as an input, not to produce that object.

By invoking notions from algorithmic randomness and considering recognizability rather than computability, we connect transfinite computability to large cardinals and forcing axioms incompatible with the axiom of constructibility on the one hand and inner models for large cardinals on the other. In particular, under appropriate large cardinal assumptions, a real number is heriditarily recognizable by a pOTM if and only if it is an element of the mouse for one Woodin cardinal. This is joint work with Philipp Schlicht.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.94 Mbits/sec	839.95 MB	View	Download
WebM	640x360	546.46 kbits/sec	231.07 MB	View	Download
iPod Video	480x270	522.1 kbits/sec	220.71 MB	View	Download
MP3	44100 Hz	249.73 kbits/sec	105.69 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)