Achilles Beros' Webpage

I am a postdoc at the University of Hawaii.

My research interests include computability theory, inductive inference and grammatical inference. Within computability theory, I have a particular interest in degree theory and applications of computability theory in other fields. My research thus far in inductive inference has been applications of computability theory to answer questions relevant to objects in inductive inference. Grammatical inference is concerned with the identification of generative grammars for languages.

I completed my Ph.D. under the supervision of Steffen Lempp and Leo Harrington.

My CV is available here, my publication list here and my research statement here

My research interests include computability theory, inductive inference and grammatical inference. Within computability theory, I have a particular interest in degree theory and applications of computability theory in other fields. My research thus far in inductive inference has been applications of computability theory to answer questions relevant to objects in inductive inference. Grammatical inference is concerned with the identification of generative grammars for languages.

I completed my Ph.D. under the supervision of Steffen Lempp and Leo Harrington.

My CV is available here, my publication list here and my research statement here

Contact

Office: | 306 Keller Hall |

Office hours: | W 1:30pm-2:30pm |

Th 1:30pm-3:30pm | |

Email: | beros@math.hawaii.edu |

Publications

The number of long words with given automatic complexity

(Submitted for publication)

We prove asymptotic bounds on the number of words with different automatic complexities.

Completeness for Vacillatory Learning

(Submitted for publication)

There is a complex hierarchy of learning models that are collectively known as vacillatory learning models. Specifically, these involve varying the number of hypotheses that are output infinitely often, the size of the symmetric difference between those hypotheses and the target set and how similar those hypotheses are to one another. We establish the arithmetic complexity of these learning models.

Canonical Immunity and Genericity

(Submitted for publication)

Whereas the usual notions of immunity -- e.g., immunity, hyperimmunity, etc. -- are associated with Cohen genericity, canonical immunity, as introduced by Beros, Khan and Kjos-Hanssen, is associated instead with Mathias genericity. Specifically, every Mathias generic is canonically immune and no Cohen 2-generic computes a canonically immune set.

Controlled Cellular Automata

(To appear in Networks and Heterogeneous Media, Special Issue on Systems Biology)

Cellular Automata have been successfully used to model evolution of complex systems based on simples rules. In this paper we introduce controlled cellular automata to depict the dynamics of systems with controls that can affect their evolution. Using theory from discrete control systems, we derive results for the control of cellular automata in specific cases. The paper is mostly oriented toward two applications: fire spreading; morphogenesis and tumor growth. In both cases, we illustrate the impact of a control on the evolution of the system. For the fire, the control is assumed to be either firelines or firebreaks to prevent spreading or dumping of water, fire retardant and chemicals (foam) on the fire to neutralize it. In the case of cellular growth, the control describes mechanisms used to regulate growth factors and morphogenic events based on the existence of extracellular matrix structures called fractones. The hypothesis is that fractone distribution may coordinate the timing and location of neural cell proliferation, thereby guiding morphogenesis, at several stages of early brain development.

Co-evolving cellular automata for morphegenesis

(To appear in DCDS-B)

Morphogenesis, the shaping of an organism, is a complex biological process accomplished through an well organized interplay between growth, differentiation and cell movement.It is still today one of the major outstanding problems in the biological sciences. Pattern formation has been well-address in the literature with the development of many mathematical models including the famous reaction-diffusion ones. We here take a different approach, introducing a controlled cellular automaton in order to model the signal molecules, known as growth factors, that convey information from one cell to another during an organism's development and help maintain the viability of the adult. This control represents extracellular structures that have been associated with the regulation of stem cell proliferation and are called fractones. In this paper we introduce two co-evolving automata, one describing the perturbed diffusion of growth factors and one accounting for the rules of basic cellular functions (proliferation, differentiation, migration and apoptosis). Fractones are introduced as an external input to control the shaping of multi-cellular organisms and analyze their influence on the emerging shape. We illustrate or theory with 2 and 3 dimensional simulations. This work presents the foundation upon which to develop cellular automata as a tool to simulate the morphodynamics in embryonic development.

From eventually different functions to pandemic numberings

(To appear in the proceedings of Computability in Europe (CiE) 2018)

A function is strongly non-recursive (SNR) if it is eventually different from each recursive function. We obtain hierarchy results for the mass problems associated with computing such functions with varying growth bounds. In particular, there is no least and no greatest Muchnik degree among those of the form SNR-f consisting of SNR functions bounded by varying recursive bounds f. We show that the connection between SNR functions and canonically immune sets is, in a sense, as strong as that between DNR (diagonally non-recursive) functions and effectively immune sets. Finally, we introduce pandemic numberings, a set-theoretic dual to immunity.

A Morphogenetic Cellular Automaton

(To appear in the proceedings of the American Control Theory Conference (ACC) 2018)

How are cell proliferation and cell migration controlled to generate an embryo (and, subsequently, a fetus) with organized tissues and organs? Growth factors are crucial signaling molecules that can diffuse over a long distance to target cells and induce cell proliferation, differentiation and migration. However, the mechanisms used to regulate growth factors and morphogenic events are not well known. In this paper, we develop a mathematical model based on biological evidence of correlations between neural cell proliferation and the distribution of extracellular matrix (ECM) structures called fractones. It is hypothesized that fractone distribution may coordinate the timing and location of neural cell proliferation, thereby guiding morphogenesis, at several stages of early brain development. We propose to develop a controlled cellular automaton for simulating the complex behavior of growth factors diffusing in a perturbed manner due to the presence of fractones. This automaton will then interact with an automaton that defines rules for mitosis and exploited the interaction to control cell proliferation.

(Submitted for Publication)

We examine sets of codes such that certain properties are invariant under the choice of oracle from a range of possible oracles and establish a connection between such codes and Medvedev reductions. In examing the complexity of such sets of \emph{universal codes}, we prove completeness results at various levels of the arithmetic hierarchy as well as two general theorems for obtaining Π^{1}_{1}-completeness for sets of universal codes. Among other corollaries, we show that the set of codes for Medvedev reductions of bi-immune sets to DNC functions is Π^{1}_{1}-complete.

Classifying the Arithmetical Complexity of Teaching Models

(To appear in the proceedings of Algorithmic Learning Theory (ALT) 2016)

This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. families with finite teaching dimension, and (2) the class of uniformly r.e. families with finite positive recursive teaching dimension witnessed by a uniformly r.e. teaching sequence. We also derive the arithmetical complexity of several other decision problems in teaching.

Effective Bi-Immunity and Randomness

(To appear in the proceedings of Computability and Complexity Symposium 2017)

We study the relationship between randomness and effective bi-immunity. Greenberg and Miller have shown that for any oracle X, there are arbitrarily slow-growing DNR functions relative to X that compute no ML random set. We show that the same holds when ML randomness is replaced with effective bi-immunity. It follows that there are sequences of effective Hausdorff dimension 1 that compute no effectively bi-immune set.

We also establish an important difference between the two properties. The class Low(MLR, EBI) of oracles relative to which every ML random is effectively bi-immune contains the jump-traceable sets, and is therefore of cardinality continuum.

We also establish an important difference between the two properties. The class Low(MLR, EBI) of oracles relative to which every ML random is effectively bi-immune contains the jump-traceable sets, and is therefore of cardinality continuum.

(Submitted for Publication)

We compare the efficiency of learning using a membership oracle and learning using a teacher. We find that there is a large class of families for which the teacher provides a super-exponential efficiency gain over learning with an oracle. Furthermore, using both a teacher and an oracle provides a super-exponential gain over either learning with only an oracle and learning with only a teacher.

(To Appear in Fundamenta Informaticae)

We prove the existence of a canonical form for semi-deterministic transducers with incomparable sets of output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.

(JMLR W&CP 34 :33-48, 2014)

We prove the existence of a canonical form for semi-deterministic transducers with incomparable sets of output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.

(To Appear in the Notre Dame Journal of Formal Logic)

Given any oracle, A, we construct a basic sequence Q, computable in the jump of A, such that no A-computable real is Q-distribution-normal. A corollary to this is that there is a Δ^{0}_{n+1} basic sequence with respect to which no Δ^{0}_{n} real is distribution-normal. As a special case, there is a limit computable sequence relative to which no computable real is distribution-normal.

(Archive for Mathematical Logic, 54(5):521--530, 2015)

In **Diagonally Non-Computable Functions and Bi-Immunity**, Carl Jockusch and Andrew Lewis proved that every DNC function computes a bi-immune set. They asked whether every DNC function computes an effectively bi-immune set. We construct a DNC function that computes no effectively bi-immune set, thereby answering their question in the negative.

(Journal of Symbolic Logic, 78(4):1183--1188, 2013)

In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex^{*}_{*} and TxtFext^{*}_{*}, could be distinguished. These learning criteria place bounds neither on the number of hypotheses between which the learner is allowed to vacillate nor on the number of errors permitted, merely that both are finite. The criteria differ in that the more restrictive one, TxtFext^{*}_{*}-learning, requires that all hypotheses output infinitely often must describe the same finite variant of the correct set, while TxtFex^{*}_{*} permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that TxtFex^{*}_{*} ≠ TxtFext^{*}_{*}, thereby answering the question posed by Osherson, et al. We prove this in a strong way by exhibiting a family in TxtFex^{*}_{2}\TxtFext^{*}_{*}.

(Journal of Symbolic Logic, 79(3):908-927, 2014)

We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity for the standard notions of finite learning, learning in the limit, behaviourally correct learning and anomalous learning in the limit. In proving the Σ^{0}_{5}-completeness result for behaviourally correct learning we prove a result of independent interest; if a u.c.e. family is not learnable, for any computable learner there is a Δ^{0}_{2} enumeration witnessing failure.

Talks

A Morphogenetic Cellular Automaton

(6/27/2018)

The Complexity of Teaching and Learning Algorithms

(2/8/2018)

Machine Learning Tools and the Problems They Can Solve

(5/12/2017)

Department Colloquium

(3/27/2015)

Recursion Theory Seminar

(2/23/2015)

Mathematics Seminar

(6/11/2014)

2013 ASL North American Annual Meeting

(5/8/2013 - 5/11/2013)

AMS Sectional Meeting

(4/26/2013 - 4/28/2013)

Recursion Theory Seminar

(12/5/2012)

Logic Seminar

(11/14/2012)

Teaching

The lecture for Math 140 meets in 152 Bilger Hall, MWF 9:30am - 10:20am.

The lecture for Math 372 meets in 402 Keller Hall, MWF 11:30am - 12:20pm.

The course syllabus is available here.

The review sheet for the first midterm is available here. The solutions are here.

The review sheet for the second midterm is available here. The solutions are here.

The review sheet for the final is available here. The solutions are here.

The homework assignments (and solutions) are listed below.

**HW #1 (due on 1/14/2019) **pdf, tex, solutions

**HW #2 (due on 1/23/2019) **pdf, tex, solutions

**HW #3 (due on 1/28/2019) **pdf, tex, solutions

**HW #4 (due on 2/4/2019) **pdf, tex, solutions

**HW #5 (due on 2/18/2019) **pdf, tex, solutions

**HW #6 (due on 2/25/2019) **pdf, tex, solutions

**HW #7 (due on 3/4/2019) **pdf, tex, solutions

**HW #8 (due on 3/11/2019) **pdf, tex, solutions (Note: These solutions are incomplete).

**HW #9 (due on 4/1/2019) **pdf, tex

**HW #10 (due on 4/8/2019) **pdf, tex

**HW #11 (due on 4/17/2019) **instructions, data

**HW #12 (due on 5/1/2019) **pdf, tex

The course syllabus is available here.

The review sheet for the first midterm is available here. The solutions are here.

The review sheet for the second midterm is available here. The solutions are here.

The review sheet for the final is available here. The solutions are here.

The homework assignments (and solutions) are listed below.

Useful Programs/Scripts

For a foundations class I taught in Fall 2016, I wrote the following turing machine simulator.

I have implemented several grammatical inference and clustering algorithms in python with tkinter interfaces. I will make them available here soon.

I have designed and implemented a internetworking transfer protocol based on UDP and intended to be used for hole-punching P2P communication.

I have written a python module for executing custom cellular automata.

A colleague needed a demonstration of attracting points for complex-valued functions, so I wrote the following grapher/calculator. In the future, I will implement further functionality.

I have implemented several grammatical inference and clustering algorithms in python with tkinter interfaces. I will make them available here soon.

I have designed and implemented a internetworking transfer protocol based on UDP and intended to be used for hole-punching P2P communication.

I have written a python module for executing custom cellular automata.

A colleague needed a demonstration of attracting points for complex-valued functions, so I wrote the following grapher/calculator. In the future, I will implement further functionality.

Personal

I have many interests outside of mathematics and computer science including photography, writing poetry and snorkeling. My brother, Kostas, is also a mathematician and logician.