Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 27.03.2008 at 12:20 in S1, there is the following noon lecture:

Automorphisms of the truth-table degrees

Bernard Anderson

University of California, Berkeley

Abstract

Let X and Y be reals (infinite binary strings). We define X <=tt Y if there is a computable function f and a total computation R mapping strings of length f(n) to strings of length n such that for all n we have R(Y|f(n)) = X|n. We say X =tt Y if X <=tt Y and Y <=tt X and call these equivalence classes truth table degrees.

Let D be the set of truth table degrees. We say a bijection p from D to D is an automorphism if for all degrees x and y we have x <=tt y if and only if p(x) <=tt p(y).

We have shown that for any real X >=tt 0' there is a real Y such that Y + 0' =tt Y' =tt X. This answers a question of Mohrherr who noted it would imply that all automorphisms of the truth table degrees are fixed on a cone:

For every automorphism p there is a degree x such that for all y >=tt x we have p(y) = y.

We have also shown that there is no 2-

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010