Algorithmic Randomness on Metric Spaces and the Random Core Operation
Thomas Birch, University of Cape Town
Tuesday, 8 December 2009, 14h00, M 111 (Seminar Room)
In researching algorithmic randomness on computable metric spaces a new operation was devised. This operation which we have called the random core, allows us to "isolate" the randomness in a compact subset. We shall use the random core approach to show that if a compact subset of a computable metric space is random, then all the "randomness" of the set is contained in the boundary. This approach has made it easier for us to prove theorems about the interaction of random and non-random sets, giving us a "toolbox" for generating new random sets from old.
Reduction Functions as Strategies in Infinite Games
Prof Benedikt Löwe, University of Amsterdam, The Netherlands
Tuesday, 1 December 2009, 14h00, M 111 (Seminar Room)
In his PhD dissertation, William Wadge uncovered a beautiful structure theory for sets of real numbers by connecting continuous reduction functions with a class of infinite games. We give an introduction to the setting in which Wadge proved his results, the Baire space (the space of infinite sequences of natural numbers, homeomorphic to the irrationals) and then prove some of the fundamental theorems of Wadge's theory (connected with the Axiom of Choice).
Finally, we move beyond continuous functions and ask whether similar game representations exist for other known classes of reduction functions such as the Borel functions, the Baire class 1 functions and others. This questions has been positively answered by Brian Semmes whose results we shall describe.
On the Computational Content of Bolzano-Weierstraß
Pavol Safarik, University of Darmstadt, Germany
Thursday, 26 November 2009, 14h00, M 111 (Seminar Room)
We will apply the methods developed in the field of "proof mining" (see mainly [1]) to the Bolzano-Weierstraß theorem BW and calibrate the computational contribution of using this theorem in a proof of a combinatorial statement. Using a simple proof based on weak König's lemma (analyzed by W. A. Howard, [2]) and arithmetical comprehension (analyzed by C. Spector, [3]) we provide an explicit solution of the Gödel functional interpretation as well as the monotone functional interpretation of BW for a product space of rational intervals. In fact, we will use it to get optimal program and bound extraction theorems for proofs based on fixed instances of BW, i.e. for BW applied to fixed sequences.
References
- U. Kohlenbach. Applied Proof Theory: Proof Interpretations and their use in Mathematics. Springer Monographs in Mathematics. Springer-Verlag, Berlin, Heidelberg, New York, 2008.
- W. A. Howard. Ordinal analysis of simple cases of bar recursion. The Journal of Symbolic Logic, 46:17-31, 1981.
- C. Spector. Provably recursive functionals of analysis: a consistency proof of an analysis by extension of principles formulated in current intuitionistic mathematics. In Recursive function Theory, Proceedings of Symposia in Pure Mathematics, vol. 5 (J.C.E. Dekker (ed.)), AMS, Providence, R.I., pages 1-27, 1962.
* This is joint work with Ulrich Kohlenbach. The author gratefully acknowledges the support by the German Science Foundation (DFG Project KO 1737/5-1).
Some Recent Results on Sets of Multiplicity via Brownian Motion
Safari Mukeru, University of South Africa, Pretoria
Tuesday, 24 November 2009, 14h00, M 111 (Seminar Room)
We briefly introduce the notions of Hausdorff and Fourier dimensions. We discuss some fractal properties of Brownian motion (the doubling dimension properties and the Salemness of Brownian images among others) and we conclude with recent results (with Fouché) on the Fourier structure of Brownian zero sets. The discussion emphasizes the difficulty of computing Fourier dimensions of compact sets and some open problems on the subject are indicated.
On the Complexity of Numerical Analysis
Prof Eric Allender, Rutgers University, USA
Thursday, 5 November 2009, 16h00, M 111 (Seminar Room)
The Euclidean Traveling Salesman Problem is a well-known NP-hard problem, but some are surprised to learn that it is not known to lie in NP. This lecture will present a new upper bound on the complexity of this problem: it lies in the "counting hierarchy". The proof falls out of some more general considerations concerning arithmetic circuits, by way of a detour through the field of computation over the Real Numbers in the Blum-Shub-Smale model.
Effective Inseparability in a Topological Setting
Prof Dieter Spreen, University of Siegen, Germany
Wednesday 7 October 2009, 15h00, M 111 (Seminar Room)
As is well-known from computability theory, there are recursively enumerable sets that cannot be separated by a recursive set. Here, we consider the inseparability of one set from another set by a recursively enumerable set, in such a way that we require the existence of an algorithm that, given a recursively enumerable set, produces a witness that it does not separate the given sets.
In a topological space two disjoint sets cannot be separated by an open set if one of the two intersects the closure of the other. Starting from this observation we derive a result on the re inseparability of the index sets of two disjoint subspaces of an effectively given topological space. As will be shown, there are important consequences.
How Discontinuous is Computing Nash Equilibria?
Arno Pauly, University of Cambridge, UK
Wednesday 30 September 2009, 16h00, M 111 (Seminar Room)
Non-cooperative Game Theory offers several concepts how rational agents might behave in strategic situations. We study the associated degrees of discontinuity, in particular of the problem to produce a Nash equilibrium to a given two-player game in strategic form. As a side result, the degree of discontinuity of solving systems of linear equations is determined.
Randomness and Complexity
Prof André Nies, University of Auckland, New Zealand
Thursday 17 September 2009, 13h00, M 320 (Colloquium)
Randomness and complexity are closely connected. We consider the meaning of the two concepts in philosophy, physics, biology, and linguistics. Thereafter, we provide mathematical counterparts of the two concepts for infinite sequences of bits. We give some examples of mathematical theorems showing the close relationship between the two.
Readylog - A Logic-based Agent Programming Language for Autonomous Robots
Dr Alexander Ferrein, Robotics and Agents Research Laboratory, Duncan MacMillan Lab, UCT
Thursday 21 May 2009, 16h00, M 111 (Seminar Room)
Autonomous robots or agents acting in the real world need to be able to react intelligently to unknown situations. The problem becomes even harder when the robot is facing teams of opponents in dynamic domains like robotic soccer. In this talk we present our approach to the problem of intelligent decision making (deliberation) for robots or agents which have to decide under real-time constraints in adversarial domains, i.e. multi-agent domains where opponents have contrary goals and try to foil the goals of the opposing team. Our application domain is the robotic soccer domain. We present the agent programming language Readylog as our approach to intelligent decision making, especially suited for dynamic real-time domains. It is based on the situation calculus and especially makes use of decision-theoretic planning as a means to intelligent decision making. Further we show, how tactical behaviours can be formalised with Readylog.
Alan Turing and the Foundations of Computable Analysis
Dr Guido Gherardi, University Bologna, Italy
Friday 24 April 2009, 16h00, M 111 (Seminar Room)
The name of Alan Turing is usually associated with the notion of computable integer function. In reality Turing was mainly interested in real numbers. His work anticipates basic ideas and results of contemporary computable analysis, but his contributions to this subject have been underestimated and almost forgotten for years. Only after the recent big development of the field we are finally able to appreciate the value of his work. We will present an overview of some of the fundamental intuitions that have become foundations for modern computable analysis.
Semantics for Languages Combining Probability and Nondeterminism
Prof Klaus Keimel, University of Darmstadt, Germany
Thursday 5 March 2009, 16h00, M 111 (Seminar Room)
The talk will summarize joint work with R. Tix, G. Plotkin and T. Streicher on semantics for languages combining probabilistic and purely nondeterministic choice. As an example one may consider the basic imperative programming language LL_p whose syntax is given (in BNF-form) by
P ::= a | P;P | cond(b,P,P) | while(b,P) | P p_⊕ P | P [] P
where b ranges over a set BExp of boolean expressions, a ranges over a set Act of basic actions and p is a real number with 0 < p < 1. Here cond(b,P,Q) stands for the conditional usually denoted as if b then P else Q fi. and while(b,P) for the while loop usually denoted as while b do P od. The program P [] Q nondeterministically executes either P or Q. The program P p_⊕ Q executes P with probability p and Q with probability 1-p.
The semantics is based on domain theoretical methods in the sense of D.S. Scott. The essential steps are the definition of a probabilistic powerdomain and - on top of it - a powerdomain adding nondeterminism, where nondeterminism can be angelic, demonic or a combination of both. The direct or state transformer semantics associates to every state in the domain of states an element of this powerdomain in a continuous way. An equivalent predicate transformer semantics including healthiness conditions will be presented.
Card Shuffles, Random Walks on Groups and Increasing Subsequences in Random Permutations
Prof Ross Pinsky, Technion-Israel Institute of Technology, Haifa, Israel
Thursday 26 February 2009, 16h00, M 111 (Seminar Room)
We consider various shuffling schemes for a deck of cards. Such a scheme can be thought of as a random walk on the symmetric group S_n with a certain transition distribution Q. Starting from the identity permutation, the distribution of the random walk (state of the deck) at step (shuffle) m is Q^m*, the m-fold convolution of the probability measure Q. The uniform distribution U_n is invariant for the random walk, so assuming the appropriate regularity conditions, Q^m* converges to U_n as m goes to infinity. One wants to know how fast the convergence is, asymptotically in n. That is, how large does m_n have to be so that ||Q^m_n*-U_n||_TV converges to 0 as n goes to infinity?
(|| ||_TV denotes the total variation norm.)
When one attempts to do this for the so-called random to random shuffle, one is led naturally to study the increasing subsequences in random permutations. In the second half of the talk I present some recent results of mine concerning increasing subsequences in random permutations.