# All posts by admin

# Permutations of the integers and Aut($\mathcal D_T$)

Two papers on restrictions on automorphisms of Turing and truth-table degrees appeared in the Downey Festschrift for the Computability and Complexity Symposium 2017 in honour of Rod Downey’s 60th birthday.

One, “Permutations of the integers induce only the trivial automorphism of the Turing degrees”, appeared in Bulletin of Symbolic Logic (2018), and was presented at Workshop on Computability Theory in Waterloo, Ontario, and Workshop on Computability Theory and Foundations of Mathematics (CTFM) in Tokyo.

# The Turing Guide and computability in physics

A draft of my review for the Notices of the AMS (2019).

# Moderator @ Theoretical Computer Science

In 2018 I was elected Moderator of the Stack Exchange Q&A site for Theoretical Computer Science,

cstheory.stackexchange.com

This site is to the theory groups in CS departments as MathOverflow is to math departments.

Computability theory is welcome… visit the site today.

# Automatic Complexity 2014-2019

The Simons Foundation under the program Collaboration Grants for Mathematicians (#315188 to Bjørn Kjos-Hanssen, grant title “Automatic Complexity”) supported my travel during 2014–2019.

Year | Trips |
---|---|

2014 – 2015 | COCOA 2014 (Maui); U. Washington; Varieties of Algorithmic Information; CCR, Heidelberg; Haidar to Arizona Winter School |

2015 – 2016 | ASL Annual Meeting, UConn (myself and Beros); SIAM Meeting on Discrete Math, Atlanta |

2016 – 2017 | WoLLIC, London; UCNC, Arkansas |

2017 – 2018 | Workshop on Computability Theory, Waterloo |

2018 – 2019 | Computability Theory and Foundations of Mathematics, Tokyo; Joint Math Meetings, Baltimore |

#### Nine subprojects

Here are papers produced about automatic complexity, many with Master’s students.

Conferences in parentheses are those with no published proceedings.

Students or consultants in parentheses discussed the topic but were not coauthors.

Student/consultant | Conference | Journal |
---|---|---|

Hyde (MA, 2013) | COCOON 2014 | Elec. J. Combinatorics (2015) |

COCOA 2014 | Theoretical Computer Science (2015) | |

Alikhani (MA, 2014); Pakravan, Saadat (MSc Fin.Eng., 2013) | Algorithmic Finance (2015) | |

(written at CCR 2015) | Theory of Computing Systems (2017) | |

(Castiglione 2015) | WoLLIC 2017 | Discrete Mathematics (2018) |

(Kobayashi 2016) | (VAI 2015) | Experimental Mathematics (2019) |

(Huggins 2016) | UCNC 2017 | |

Liu (MA, 2017) | (ALH 2018) | |

Yogi (MA, 2018) |

For instance, I gave a talk in the Seattle Probability Seminar organized by Soumik Pal and Chris Burdzy at the University of Washington Department of Mathematics.

Title:

Kolmogorov structure functions for automatic complexity

Abstract:

We study an analogue of Kolmogorov’s notion of structure function, introduced in 1973, with Kolmogorov complexity replaced by Shallit and Wang’s (2001) automatic complexity. We discuss the prospects for using it for model selection in statistics. We prove an upper bound which is piecewise smooth, related to the binary entropy function, and appears to be fairly sharp based on numerical evidence.

The paper is loosely coupled with the following software:

- Complexity Guessing Game

- Complexity Option Game

- Structure Function Calculator

These are gathered in some slides.com slides.

# The number of languages with maximum state complexity

Lei Liu completed her Master’s degree with the project title *Complexity of Options* in 2017.

Now we are working on an extension to monotone options (pictured) which will be presented at

ALH-2018. The new paper is called **The number of languages with maximum state complexity**.

# Long words with given complexity

Kaui Yogi completed his Master project in Spring 2018. With Achilles Beros we have a new paper on *The number of long words with given automatic complexity* based in part on Yogi’s project work.

# Deontic Logic and proof assistants

*Damir Dzhafarov, Stefan Kaufmann, Bjørn Kjos-Hanssen, Dave Ripley, et al., at the 2016 ASL Annual Meeting at UConn.*

José Carmo and Andrew J.I. Jones have studied contrary-to-duties obligations in a series of papers.

They develop a logical framework for scenarios such as the following:

1. There ought to be no dog.

2. If there is a dog, there ought to be a fence.

One conjecture from Carmo and Jones 1997 was refuted in a rather technical way in my 1996 term paper at University of Oslo.

The conjecture stated that one could simply add the condition

$\DeclareMathOperator{\pii}{ob}$

$$

(Z \in \pii(X)) \land

(Y \subseteq X) \land

(Y \cap Z \ne \emptyset ) \rightarrow (Z \in \pii(Y )) \tag{5e}

$$

for the conditional obligation operator ob.

In a follow-up paper (2001) they argued that (5e) could be added by weakening some other conditions.

In a new paper in Studia Logica, and presented at the Association for Symbolic Logic Annual Meeting 2016 at UConn, I argue that (5d) and (5e) are in conflict with each other. The argument is a generalization and strengthening of the 1996 argument.

2018: Benzmüller et al. have implemented Carmo and Jones’ logic in the proof assistant Isabelle.