Algorithmic Complexity and Effectively Closed Classes

Stephen Binns Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals

October 2007

Contents

1 Introduction 2 1.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Algorithmic complexity theory . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Main proposal 4 2.1 Focus of research, literature review and references . . . . . . . . . . . . . 4 2.2 Description of Proposed Research . . . . . . . . . . . . . . . . . . . . . . 8

3 Supplementary Material 12 3.1 Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Project Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Monitoring and Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.5 Utilisation plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.6 Personnel Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.7 List of potential reviewers . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 CV of Principal Investigator 14

5 Budget 17

1 Introduction

1.1 Abstract

We propose basic research in the area of algorithmic complexity and computability theory.

This field of study has historically been of interest to both computer scientists and mathematical logicians and there is currently a resurgence of research in the area, with recent international conferences having taken place in Argentina, The United States, China and Germany. A major research grant by the United States’ National Science Foundation has recently been awarded, and publications are appearing in many major journals of computer science and mathematics. There is a lot of potential for basic research of this type to have ramifications in many different areas of mathematics and computer science.

We propose here to concentrate on the relationship between algorithmic complexity and effectively closed subclasses of the Cantor space. In particular we will study diminutive classes and explicate their relationship to Kolmogorov complexity. Diminutiveness is a computability-theoretic notion and is a generalisation of the idea of being 0-dimensional in the sense of Hausdorff.

We intend that this research build on previous work in the area and to point towards future directions of investigation. The results of the research will be applicable to other areas in computability theory, have ramifications for the study of the Muchnik degrees and shed light on some aspects of computable algebra and other areas of logic and mathematics. We intend in particular to investigate the relationship between diminutive, effectively closed classes and effectively presented Boolean algebras, completions of logical theories and aspects of symbolic dynamics.

The proposal will take place over the period of one year and include attending meetings abroad, collaborating with distinguished international researchers and publishing results in academic journals.

1.2 Algorithmic complexity theory

Algorithmic complexity theory^{1} is a branch of computability theory in mathematical logic. It attempts to describe the quality of information contained in binary strings and sequences. The quantity of information contained in an infinite binary sequence (usually called a real) has been studied for decades, beginning with the seminal work of Alan Turing in the 1930s. Turing’s conception was that for a real X, this quantity could be measured by describing what one was able to compute (on a Turing machine) using X. What is meant by the quality of information is harder to pin down but one approach, the approach we take here, is to look at the Kolmogorov complexity of strings.

1Credit for the founding work in this area is usually shared between Andrey Kolmogorov, Gregory Chaitin, Ray Solomonoff and Leonid Levin

If σ is a binary string, then the Kolmogorov complexity K(σ) of σ is defined to be the length of the shortest possible description of the string^{2}. This definition of course pivots of the exact definition of description we use, and there are indeed various distinct formulations of this notion. But the basic idea is intuitive: a long string of random 0s and 1s given by, say, the tossing of a fair coin will probably have no description significantly shorter than the length of the string - there will be no way to describe it other than by explicitly giving the value of each bit. A long string consisting only of 0s on the other hand could be described simply by giving little more information than the length of the string.

Using Kolmogorov complexity, one can obtain a precise formulation of the idea of randomness: a random string is one which has no description shorter than its own length. A random (infinite) binary sequence is then one all of whose initial segments are random. Straightforward arguments show that almost all binary sequences are random. This definition of randomness, while by no means the only possible definition, has a distinct robustness about it and different conceptions of randomness such as the measure theoretical approach of Martin-Löf or the betting strategy approach of Lutz and others have been proved equivalent. Connections have also been established with traditional ideas of randomness such as Brownian motion [16].

One of the most resonant discoveries in the field is the connection between Hausdorff dimension and Komolgorov complexity. In computability theory we often have effective or computable versions of classical notions. In particular, computability theory has effective notions of having positive measure or Hausdorff dimension. On some particularly nicely defined classes - for instance the effectively closed (or Π_{1}^{0}) classes - the effective and classical notions will coincide, but other classes they will not. Indeed it is possible that even singleton reals will have positive dimension or measure. In fact a real is random precisely when it has positive effective measure. It turns out that the effective Hausdorff dimension of a real is precisely the limit infimum of the information density of its initial segments. That is, the Hausdorff dimension of a singleton real {X} is

lim inf_{n→∞} \frac{K(X ↾ n)}{n}.

For any class of reals C, the effective Hausdorff dimension of C is the supremum of the effective Hausdorff dimension of its elements. And so if C is effectively closed, the classical Hausdorff dimension of C is,

sup_{X∈C} lim inf_{n} \frac{K(X ↾ n)}{n}.

This identity is significant in that it gives an computability-theoretic formulation for a purely classical notion (Hausdorff dimension). The result is more striking when one realises that many simple examples of fractal objects - such as the Cantor middle third set, the Menger sponge or Sierpinski gasket - are effectively closed classes^{3} and hence their Hausdorff dimensions are given by the information-theoretic complexity of their elements.

2For correctness it should be noted that K(σ) here is actually the prefix-free complexity of σ. The details of the difference between prefix-free complexity and plain complexity are important but are suppressed here.

In the research proposal outlined below, we look especially at an extension of the class of reals of positive Hausdorff dimension - the class of so-called complex reals. This notion, only very recently formulated^{4}, is already leading to significant results in the field. The definition is as follows:

Definition 1.1. A real X is complex if there is a computable function f such that for all n

K(X ↾ f(n)) ⩾ n.

It is then straightforward to show that reals of positive Hausdorff dimension must be complex. Complex reals have the interesting property that the can be defined without any reference to Kolmogorov complexity at all. In [26] it is shown that X is complex if and only if X ⩾_{wtt} Y, for some DNR function Y. We propose to use complex reals as a starting point to research into algorithmic complexity theory.

2 Main proposal

2.1 Focus of research, literature review and references

As some of the following ideas have not appeared widely in the literature to date, we provide a brief summary of the main definitions and results on which we are basing our proposal. We let ω represent the set of natural numbers, 2^{<ω} the set of finite binary strings, and 2^{ω} the class of infinite binary sequences. Unexplained terminology can be found in [18] or [25].

The basic definition here is that of a computably perfect class. In a general topological space, a set is perfect if it is closed and has no isolated points. A closed subclass of 2^{ω} is perfect if for all P -extendible nodes σ ∈ 2^{<ω}, there are at least two incomparable P -extendible nodes extending σ. (A node σ ∈ 2^{<ω} is P -extendible if s can be extended to some element of P). We will be using extensively the following effective version.

Definition 2.1. A closed set P ⊆ 2^{ω} is computably perfect^{5} if there is a computable function f such that for all n and all P -extendible nodes σ ∈ 2^{<ω} of length n, there are at least two incomparable P -extendible nodes extending σ of length bounded by f(n). We say f witnesses the perfection of P.

3Strictly speaking these objects are not classes of binary sequences but are subclasses of ℝ^{n}. This turns out to be of little significance as results in the field are easily transferred to any compact complete separable metric space.

4in [26]

5Although not common in the literature, the notion of computable perfection is not new here and has appeared under different names in [2], [11] and [17].

Any given closed subclass of 2^{ω} may or may not be computably perfect, but we will be particularly concerned with effectively closed, or Π_{1}^{0}, classes.

Definition 2.2. A Π_{1}^{0} class is diminutive if it does not contain a computably perfect Π_{1}^{0} subclass.

It is shown in [3] ^{6} that some commonly studied types of Π_{1}^{0} classes are diminutive. For example thin classes (see [5] or [19]), small, and e.p.h.i. classes (see [2]), countable classes ([24], [27]) and Π_{1}^{0} classes of pairwise Turing incomparable elements (see [12]). On the other hand, classes of positive Hausdorff dimension or measure are not diminutive (Theorem 3.25 [17]).

In [3] we establish the following characterisation of diminutive classes:

Theorem 2.3. If P ⊆ 2^{ω} is a Π_{1}^{0} subclass of 2^{ω}, then the following are equivalent

1. P is not diminutive

2. P contains a complex element,

3. P contains a wtt-cover for 2^{ω} (that is for all X ∈ 2^{ω} there is a Y ∈ P such that Y ⩾_{wtt} X).

This result speaks to several independent previous lines of research. Firstly it extends the Kučera-Gács theorem (see [13], [10]) which states that every real is wtt-reducible to some Martin-Löf random. Furthermore it characterises exactly which Π_{1}^{0} classes have this property.

Secondly, it is a counterpart to the theorem of Kučera’s that a Π_{1}^{0} class has positive measure if and only if it contains a Martin-Löf random real. Here instead of randomness and positive measure we have the weaker properties of complexity and nondiminutiveness. Both theorems relate a global notion of size with the local property of containing an element of a certain minimal Kolmogorov complexity. A real X is random if K(X ↾ n) ⩾ n − O(1) and X can be seen to be complex if for all n K(X ↾ n) ⩾ f(n) for some computable unbounded nondecreasing f, so the analogy is clear. The connection between classes of positive measure and non-diminutive classes is less immediate as diminutive classes seem to be more analogous to countable classes that to those of zero measure - a closed class is uncountable if and only if it has a perfect subclass, a closed class is non-diminutive if and only if it has a computably perfect subclass.

This speaks to another connection to an independent line of research - namely that of countable Π_{1}^{0} classes. Such classes have been studied in [24], [27], and elsewhere.

6This preprint can be obtained at http://www.math.dartmouth.edu/∼frg/papers.html

Elements of countable Π_{1}^{0} classes are called ranked. If the analogy of diminutive classes to countable classes is fruitful, then there should be connections between ranked reals and elements of diminutive classes - which we dub weakly ranked. For example, it follows from work in [2] that the class of weakly ranked reals is closed under tt-reductions, as is the class of ranked reals. A recent result of Reimann and Slaman (personal correspondence) gives a construction of an NCR_{1} real that is not ranked. The real is constructed explicitly as an element of a diminutive Π_{1}^{0} class (although this terminology is not used) and so the natural question arises whether every NCR_{1} is weakly ranked.

Diminutive classes have often appeared implicitly in the literature in the context of forcing with computable perfect trees; for example in the construction in [12] of a Π_{1}^{0} class where any two distinct elements are Turing incomparable. This is a typical example of a straightforward forcing argument and in [3] we show that any such class is diminutive (if it were not, then by Theorem 2.3 it would have a wtt-cover of the reals and some element of it would be wtt-reducible to another distinct element). Although in no way could we say that every such forcing argument produced a diminutive class, it could be expected that many common constructions do produce such classes. It should thus be profitable to prove general theorems about diminutive classes as these could then have consequences for a broad array of constructions. Indeed many types of minimality arguments use such constructions and so we can ask questions such as whether every diminutive class contains an element of minimal Turing degree. (The question of whether every such minimal element belongs to a diminutive class would seem to be false as the minimal element constructed in [14] is apparently a counterexample, being both minimal and recursively bounded DNR and hence complex by [26]).

Another recent area that has been of some interest to researchers lately is that of Muchnik degrees. Two Π_{1}^{0} classes P and Q are said to be Muchnik equivalent (and hence have the same Muchnik degree) if every element of one class, Turing computes an element of the other. The resulting collection of equivalence classes forms a degree structure called the Muchnik lattice. There are many possible questions one can ask about the position of the diminutive classes within this structure and a similar analysis has been carried out for small classes in [1].

Much has been written about so-called natural Muchnik degrees (see for example [21][22] and [20]). It is an interesting property of the Muchnik lattice that there exists easily definable and mathematically interesting examples of intermediate degrees. Up until recently all examples of these natural degrees have been above the Muchnik degree of DNR. No Π_{1}^{0} class Muchnik above DNR can be diminutive (as each class will contain a hyperimmune-free element which wtt-computes a DNR function and which is hence complex by [26]). Joshua Cole and Stephen Simpson have however produced natural examples of degrees that are not Muchnik above DNR (see [6]). This raises questions about whether such classes are diminutive or not.

It is also possible, however, that the Muchnik lattice may not be the most suitable degree structure in which to pose questions about diminutive classes. There are two reasons for this. The first is that it is not the case that diminutiveness is an invariant of Muchnik degree. That is, it is possible that P be diminutive, Q Muchnik equivalent to P, and Q not diminutive. In fact if P is any dimunitive class, then P ∨ 2^{ω} := {X ⊕ Y : X ∈ P ∧ Y ∈ 2^{ω}} is computably perfect and hence not diminutive.

The second reason for this may be seen by taking the example of the countable Π_{1}^{0} classes - an important type of diminutive class. Every countable Π_{1}^{0} class contains a computable element and hence has trivial Muchnik degree. However this does not preclude important and interesting questions being asked about the degree of ranked reals. In light of Theorem 2.3, one might suggest the following degree structure: for any Π_{1}^{0} classes P and Q, P is x-equivalent to Q if every element of P is wtt-reducible to some element of Q and vice versa. Again by Theorem 2.3, all Π_{1}^{0} classes that contain a complex element (including all those Muchnik above DNR) have maximum x-degree (they contain wtt-covers of 2^{ω}) and all Π_{1}^{0} classes with only computable elements have minimum degree. So a Π_{1}^{0} class has intermediate x-degree if and only if it is diminutive and has at least one noncomputable element. One may ask whether there are any natural degrees in this structure. The classes constructed by Simpson and Cole are a sensible place to start.

Finally we point out the connection of some of this work to results in computable model theory. This line of research begins with a paper by Chisholm, Chubb, Harizanov, Hirschfeldt, Jockusch, McNichol, and Pingrey [15]. The paper looks at scattered linear orders - linear orders with no copy of ℚ as a suborder. If a linear order is computable (that is if its order relation and underlying set form computable sets), then its class of (characteristic functions of) initial segments form a Π_{1}^{0} class. and this class is countable if and only if the linear order is scattered. Thus every initial segment of a scattered linear ordering is a ranked set. It is pointed out in the paper that any Π_{1}^{0} class with a complex element is uncountable and hence no scattered linear order contains a complex initial segment. Theorem 2.3 above allows us to extend this result and describe under what circumstances the converse holds. Namely, a computable linear order has a complex initial segment if and only if its class of initial segments contains a computably perfect subclass. It can be shown that there are scattered linear orders with uncountably many initial segments but no complex initial segment (see [3]). It is possible however to characterise those linear orders as follows:

Definition 2.4. A computable linear order =⟨ω, ⩽_{L}⟩ is weakly scattered if there is no computable function f such that for all n ∈ ω, if a, b ⩽ n, with a <_{L} b, then there is x, y, z ≤ f(n) such that

x <_{L} a <_{L} y <_{L} b <_{L} z.

In other words, L is weakly scattered if it has no computable witness to the fact that it is a dense linear order without endpoints. Thus weakly scattered linear orders are to scattered linear orders as weakly ranked reals are to ranked reals, as diminutive classes are to countable classes. Thus by theorem 2.3, weakly scattered computable linear orders can be characterised in any of three ways: by the existence of the computable witness as above, by the existence of a complex initial segment, or by the fact that any real is wtt-reducible to some initial segment.

It is to be expected that similar results could be obtained in other areas of computable structures - ultrafilters in effective Boolean algebras, or completions of logical theories . Both of these examples are closely related to Π_{1}^{0} classes - for example thin Π_{1}^{0} classes have already been shown to correspond to maximal theories. Some interesting work has been recently done on effective symbolic dynamics (see [7] and [23]) and this would also seem a natural area of investigation. Π_{1}^{0} classes occur endemically in many areas of effective mathematics (see [4]), and any one of these areas could be a fruitful place to apply these concepts of complexity theory and diminutive classes.

2.2 Description of Proposed Research

We propose to base our research around the investigation of the nexus of complexity and Π_{1}^{0} classes, concentrating on diminutive classes. We now detail more closely the areas and questions we intend to concentrate on.

1. Diminutive classes. We first intend to investigate the general properties of diminutive classes. Three questions seem to stand out as ones that could be immediately addressed.

• Does every diminutive class with no computable element contain an element of minimal Turing degree? Is it possible to characterise those that do?

• When forcing with computably perfect trees, what properties of the forcing conditions will result in the construction a diminutive Π_{1}^{0} class?

• The relationships between various kinds of diminutive classes have been studied in [2] and will not be concentrated on in this project, however there is one outstanding question that may be addressed and that is whether every thin Π_{1}^{0} class is small. Some progress was made in [3] where it was shown that every thin class is e.p.h.i.

2. Ranked vs weakly ranked. The basic research program here is to investigate which properties of ranked reals are shared by weakly ranked reals.

• As there are only countably many ranked sets, it is easy to see that there are reals that are not wtt-reducible to any ranked real. Every real is wtt-reducible to some non-weakly ranked real (in fact some random real by the Kučera-Gács Theorem). Is it the case, however, that every real is wtt-reducible to some weakly ranked real?

• Is every NCR_{1} real weakly ranked?

• In [15] It is shown that every uniformly ANC degree computes a set D that is not wtt-reducible to any ranked set. Does this hold for weakly ranked sets?

3. Muchnik and x-degree structures. One may ask many questions about the Muchnik degrees of diminutive classes and there are similarly many questions about the basic structure of the x-degrees. It is not our claim that all these questions will lead to significant mathematical progress, however a sketch of some of the basic ideas should lead to further insight into the area. Two questions we find particularly work investigation.

• Is it possible to classify the Muchnik degrees of various types of diminutive classes? Do any natural examples of diminutive Muchnik degrees (degrees with diminutive representatives) exist?

• Are there any natural examples of intermediate x-degrees?

4. Computable algebra. Although scattered linear orders provide an interesting example of the use of complexity theory and diminutive classes, there should be other examples where Theorem 2.3 is used with equally as profitably.

• What other computable structures exhibit a connection between algorithmic complexity and wtt-degree spectra? For example, are the above results applicable to computable partial orders? Is there a similar formulation for countable Boolean Algebras and their ultrafilters? Or logical theories and their completions.

References

[1] Stephen Binns. The Medvedev and Muchnik Lattices of Π_{1}^{0} classes. PhD thesis, The Pennsylvania State University, 2003. 80 pages.

[2] Stephen Binns. Hyperimmunity in 2^{ω}. Notre Dame Journal of Formal Logic, 48(2):293–316, 2007.

[3] Stephen Binns. Π_{1}^{0} classes with complex elements. preprint, 2007.

[4] Douglas Cenzer and Jeffrey B. Remmel. Π_{1}^{0} classes in mathematics. In [9], pages 623–821, 1998.

[5] Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann. Automorphisms of the lattice of Π_{1}^{0} classes; perfect thin classes and ANC degrees. September 2000. Preprint, 33 pages.

[6] Joshua Cole and Stephen G. Simpson. Mass problems and hyperarithmeticity. page preprint.

[7] Ali Dashti Douglas Cenzer and Jonathan L.F. King. Effective symbolic dynamics. Electronic Notes in Theoretical Computer Science (electronically published), 2007. URL: www.elsevier.nl/locate/entcs.

[8] H.-D. Ebbinghaus, G.H. Müller, and G.E. Sacks, editors. Recursion Theory Week. Number 1141 in Lecture Notes in Mathematics. Springer-Verlag, 1985. IX + 418 pages.

[9] Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors. Handbook of Recursive Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, 1998. Volumes 1 and 2, XLVI + 1372 pages.

[10] P. Gács. Every sequence is reducible to a random one. Information and Control, 70:186–192, 1986.

[11] Peter Hertling. Surjective functions on computably growing Cantor sets. Journal of Universal Computer Science, 3(11):1126–1240, 1997.

[12] Carl G. Jockusch, Jr. and Robert I. Soare. Π_{1}^{0} classes and degrees of theories. Transactions of the American Mathematical Society, 173:35–56, 1972.

[13] Antonín Kučera. Measure, Π_{1}^{0} classes and complete extensions of PA. In [8], pages 245–259, 1985.

[14] Andrew Lewis Masahiro Kumabe. A fixed point free minimal degree. 2007. Preprint,.

[15] John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch Jr, Timothy McNicholl and Sarah Pingrey. Π_{1}^{0} classes and strong degree spectra of relations. Journal of Symbolic Logic, 72:1003–1018, 2007. to appear.

[16] Bjørn Kjos-Hanssen, Anil Nerode. The law of the iterated logorithm for algorithmically random Brownian motion. LFCS 2007: Symposium on Logical Foundations of Computer Science, Proceedings. Lecture Notes in Computer Science, 4514, 2007.

[17] Jan Reimann. Computability and Fractal dimension. PhD thesis, Ruprecht-Karls-Universität, Heidelberg, 2004. 130 pages.

[18] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. XIX + 482 pages.

[19] Douglas Cenzer, Rodney Downey, Carl Jockusch, Richard A. Shore. Countable thin Π_{1}^{0} classes . Annals of Pure and Applied Logic, 59:79–139, 1993.

[20] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, pages 29 pages, to appear.

[21] Stephen G. Simpson. Some fundamental issues concerning degrees of unsolvability. Computational Prospects of Infinity, Lecture note series.

[22] Stephen G. Simpson. An extension of the recursively enumerabe turing degrees. Journal of the London Mathematical Society, 75:287–297, April 2007.

[23] Stephen G. Simpson. Medvedev degrees of 2-dimensional subshifts of finite type. 2007. preprint.

[24] Douglas Cenzer, Rick L. Smith. On the ranked points of a Π_{1}^{0} set. The Journal of Symbolic Logic, 54(3):975–991, 1989.

[25] Robert I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag, 1987. XVIII + 437 pages.

[26] Bjørn Kjos-Hanssen, Wolgang Merkle, Frank Stephan. Komolgorov complexity and the recursion theorem. Lecture Notes in Computer Science, 3884, pages 149–161, 2006.

[27] Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare, Richard A. Shore, Stanley S. Wainer. Members of countable Π_{1}^{0} classes. Annals of Pure and Applied Logic, 31(2-3):145–163, 1986.

3 Supplementary Material

3.1 Schedule

The following is a provisional schedule for the implementation of the research proposal. It is approximate only and may change if the obtained results warrant this. To a certain extent the timetable will also be contingent on scheduling constraints of the international collaborators.

1. February - April 2008

Description of the basic properties of diminutive classes and investigation of their relationship with minimal degrees and forcing with perfect trees.

2. May - July 2008

Investigation of the relationship between ranked and weakly ranked reals.

3. August - November 2008

Elucidation of the Muchnik and x-degree structure of diminutive classes

4. November 2008 - February 2009

Investigation into issues in a wider mathematical context that may be impacted by diminutive classes. In particular, as indicated in the research proposal, we will look at completions of logical theories and symbolic dynamics.

3.2 Project Objectives

The main output of the project will be publication of results in major journals of mathematical logic and computer science. Formal and informal presentations of results at international meetings of researchers are to be expected. We will also contribute papers and preprints to research community websites and discussion groups, and participate in the informal academic community involved in research in this area.

3.3 Monitoring and Evaluation

The project will be evaluated on the degree to which the above objectives have been met. To a certain degree the direction of research will depend on results obtained, and some areas of the proposed study will be concentrated on and other, less promising, directions will be worked on less. Detailed reports on progress will be provided when required.

3.4 Experimental Design

Not applicable

3.5 Utilisation plan

Not applicable

3.6 Personnel Requirements

The project manager is the sole investigator in this project.

3.7 List of potential reviewers

Dr Joseph Miller  Dr Bjørn Kjos-Hanssen
Department of Mathematics  Department of Mathematics
University of Connecticut  University of Hawaii
Storrs CT 06269 USA  Honolulu 96822, USA
josephmiller@math.uconn.edu  bjoern@math.hawaii.edu
Dr Stephen Simpson  Dr Reed Solomon
Department of Mathematics  Department of Mathematics
The Pennsylvania State University University of Connecticut
State College PA 16802, USA  Storrs CT 06269, USA
simpson@math.psu.edu  solomon@math.uconn.edu
Dr Jan Reimann  Dr Rebecca Weber
Department of Mathematics  Department of Mathematics
University of California, Berkeley Dartmouth University
Berkeley CA 94720, USA  Hanover NH 03755, USA
reimann@math.berkeley.edu  rebecca.weber@dartmouth.edu
Dr Denis Hirschfeldt  Dr Douglas Cenzer
Department of Mathematics  Department Of Mathematics
University of Chicago  University of Florida
5734 S.University Ave.  PO Box 118105
Chicago IL 60637, USA  Gainesville, FL 32611, USA
drh@math.uchicago.edu  cenzer@math.ufl.edu

4 CV of Principal Investigator

Curriculum Vitae

Stephen Binns

Personal Details:

Name:  Stephen Ernest Binns
Nationality:  New Zealander
Address:  (home)

PO Box 1181 Dhahran, 31261 Saudi Arabia

(office) Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals PO Box 5046 Dhahran, 31261 Saudi Arabia

Phone:  +966 3 860 6074 (home)

+966 3 860 2720 (office)

email  binns@kfupm.edu.sa
homepage:  http://faculty.kfupm.edu.sa/math/binns

Position:  Assistant Professor, Department of Mathematics and Statistics

King Fahd University of Petroleum and Minerals.

Previous Position: Post-doctoral fellow, Department of Mathematics

University of Connecticut, USA.

Research Interests: Logic and foundational studies,

computability theory, algorithmic complexity theory.

Education:  PhD (Mathematics) 2003

The Pennsylvania State University, USA Thesis Advisor: Stephen G. Simpson Thesis title: The Medvedev and Muchnik Lattices of Π_{1}^{0} classes.

MA (Mathematics), 1997 Victoria University of Wellington New Zealand Advisor: Robert Goldblatt.

BA (Mathematics, Scandinavian Studies), 1989 Auckland University New Zealand

Publications:  Below Weak König’s Lemma

(with Kjos-Hanssen and Slaman) (in preparation).

Π_{1}^{0} classes with complex elements. (submitted Sept 2007, Journal of Symbolic Logic).

Self-embedding of computable trees (with Kjos-Hanssen, Lerman, Schmerl and Solomon) Notre Dame Journal of Formal Logic (to appear).

Hyperimmunity in 2^{ω}, Notre Dame Journal of Formal Logic, 2007 Volume 48, Number 2, 293-316.

On a conjecture of Dobrinen and Simpson concerning almost everywhere domination (with Kjos-Hanssen, Lerman and Solomon), Journal of Symbolic Logic (Vol 71, March 2006).

Small Π_{1}^{0} classes, Archive for Mathematical Logic (Vol 45, May 2006).

Publications : Embeddings into the Medevdev and Muchnik lattices
(continued)  of Π_{1}^{0} classes (with Stephen Simpson),

Archive for Mathematical Logic, Vol 43, Number 3, April 2004.

A Splitting Theorem for the Medvedev and Muchnik Lattices Mathematical Logic Quarterly, Vol 49, Issue 4, May 2003.

Presentations: VSMALL-A subsystem of second-order arithmetic

AMS Sectional Meeting Storrs 2006.

Fast growing trees Connecticut Logic Seminar 2005.

Small Π_{1}^{0} Classes Penn State Logic Seminar 2002.

The Medvedev and Muchnik Lattices AMS Sectional Meeting University of Wisconsin 2002.

Awards:  Charles H. Hoover Memorial Teaching Award

PSU Mathematics Department 2002.

Associaion of Symbolic Logic, Travel award Logic Colloquium, Helsinki 2003.

Mid-Atlantic Mathematical Logic Seminar: Travel award MAMLS conference Washington DC 2001.

Association of Symbolic Logic, Travel award ASL conference Philadelphia 2001.

Teaching:  Elementary Discrete Mathematics, Basic Calculus and Algebra,

Multivariable Calculus, Differential Equations, Linear Algebra, Introduction to Mathematical Proof, Logic.

5 Budget

KFUPM Internal Research Proposal

Project Name: Algorithmic Complexity and Effectively Closed Classes.

Project manager: Stephen Binns

Project dates: Feb 2008 - Feb 2009

Budget Items:

1. Compensation (@ 1200SR per month): 14400 SR
2. Travel and Visitors:  20000 SR
3. Conference Attendance:  12000 SR
4. Secretarial Work:  2000 SR
5. Printing Materials:  1000 SR
6. Miscellaneous Expenses:  2000 SR

Total:  51400 SR

Signed: Date: