Automatic complexity: a computable measure of irregularity

Add to your list(s) Download to your calendar using vCal

• Bjørn Kjos-Hanssen (University of Hawaii)
• Monday 06 June 2022, 11:15-12:15
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact nobody.

SASW09 - International conference on computability, complexity and randomness

Depending on how we define it, the “complexity” of a finite word may or may not be: 1. Computable. 2. Taking concrete values (not just up to a constant additive term). 3. Hard to compute, (1) notwithstanding. 4. Robust (admitting equivalent characterizations). Automatic complexity, introduced by Shallit and Wang in 2001, has properties (1) and (2). I will discuss the current status for (3) and (4), and what else is known and unknown about automatic complexity.  

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.