Preliminary version: The law of the iterated logarithm for algorithmically random paths of Brownian motion.
Logical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 4514, Springer, Berlin, 2007, pp. 310—317.
In this paper we answered a question of Fouché regarding algorithmically random Brownian motion. The key idea was to use Carathéodory’s measure algebra isomorphism theorem.
Mathematics 472 (Statistical Inference), University of Hawaii at Manoa, Spring 2009.
This project concerns the distribution of the nearest walk of length \(n\) to a randomly chosen walk of length \(m>n\),
where the walks have step size \(1/n\) on the \(x\)-axis and \(1/\sqrt n\) on the \(y\)-axis.
It is well known that the distribution of such walks converges to Brownian motion.
Two of the groups in the class found that strings of the form \(1^a0^b\) and \(0^a 1^b\) were the least likely nearest walks, whereas strings of the form \(0101\ldots\) or \(1010\ldots\) were the most likely. Strings of the form \(000\ldots\) or \(111\ldots\) were the second least likely.
In algorithmic randomness we try to determine what it takes to produce randomness, and what you can do with it once you have it.
Logic and computability deal with the borders between the complete and the incomplete, the decidable and the undecidable, the computable and the non-computable. A fundamental result in the area is Gödel’s 1931 incompleteness theorem, which is a precise version of the following sentiment of Ishmail in Moby Dick.
I promise nothing complete; because any human thing supposed to be complete, must for that very reason infallibly be faulty.
Laurent Bienvenu and Paul Shafer discovered an apparent error in the proof of Lemma 4.6. There it is stated that A wtt-reduces to B; however, it seems that the reduction of A to B also requires oracle access to f. Corollary 4.7 also seems false (take f to be a ML random of hyperimmune-free degree, and A=f; then A is complex but not f-complex).
Self-embeddings of computable trees (with Stephen Binns, Manuel Lerman, Jim Schmerl, and Reed Solomon). Notre Dame Journal of Formal Logic49 (2008), no. 1, 1—37.
I was probably the least-involved of the five authors of this paper, which was written in 2005-2006 at UConn.
The strength of some combinatorial principles related to Ramsey’s theorem
(with Denis R. Hirschfeldt, Carl G. Jockusch, Steffen Lempp, and Theodore A. Slaman.) Computational Prospects of Infinity. Part II: Presented Talks, Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore, vol. 15, World Scientific Publishing, Hackensack, NJ, 2008, pp. 143—162.
This paper established that Stable Ramsey’s Theorem for pairs implies DNR, which is a weak form of WKL.
It was later shown by Liu in 2011 that Ramsey’s theorem for pairs does not imply WKL (which is what we really wanted to know!).
This paper was written while all authors were participating in the Computational Prospects of Infinity workshop in Singapore in 2005.
This paper was concerned with the difference between highness and almost everywhere domination in the Turing degrees. This was taken further in later papers.
Professor of Mathematics, University of Hawaii at Manoa
