Complexity, Provability and Incompleteness
Prof Cristian S. Calude, University of Auckland, New Zealand,
Monday 28 November 2005, 11h00, M 320
In this talk we report some results, jointly obtained with H. Juergensen, regarding Chaitin's heuristic principle: 'the theorems of a finitely-specified theory cannot be significantly more complex than the theory itself'. We show that this principle is valid for an appropriate measure of complexity. We show that the measure is invariant under the change of the Goedel numbering. For this measure, the theorems of a finitely-specified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like Zermelo-Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity, hence every sentence of the theory which is significantly more complex than the theory is unprovable. Previous results showing that incompleteness is not accidental, but ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence of length n is provable in the theory tends to zero when n tends to infinity, while the probability that a sentence of length n is true is strictly positive. The talk will conclude with a few open problems
An Exotic Example of a Self-Adjoint Partial Differential Operator
Prof Atsushi Yoshikawa, Kyushu University, Japan,
Monday 21 November 2005, 10h00, Room M 200
Investigations are focused on partial differential operators which commute with certain integral operators analogous to those arising from the communication engineering. An explicit self-adjoint operator is derived for the case of disks in the plane.
"Hypercomputing" Zeno machines
Prof Petrus H. Potgieter, University of South Africa, Pretoria,
Tuesday 13 September 2005, 16h00, M 111 (Seminar Room)
The talk will briefly review the origin and application of the Church-Turing thesis (or rather, theses) and consider the oldest and perhaps the most straight-forward idea in "hypercomputation": Zeno machines. The halting problem will be discussed in a generalised context and w.r.t. to these Turing machines with accelerating clock.
(see http://arxiv.org/abs/cs/0412022)
Duality via Truth
Prof Ingrid Rewitzky, University of Stellenbosch,
Tuesday 24 May 2005, 16h00, M 111 (Seminar Room)
A type of duality - duality via truth - between classes of algebras and classes of relational systems (frames) is presented. Both classes are defined axiomatically, so they are presented at the same level of abstraction. In Stone or Priestley duality theory a class of algebras is defined in an abstract way with a set of axioms, but dual spaces can be seen as 'concrete' objects whose definition is explicitly given. Our approach is to view algebras and frames as being semantic structures for formal languages. Having a semantics we are able to define a concept of truth of formulae of a formal language. A duality principle for establishing duality via truth says that a given class of algebras and a class of frames provide equivalent semantics of a formal language whose signature coincides with the signature of the algebras in question. Consequently, the algebras and the frames express equivalent notions of truth. As examples of duality via truth we will consider two ways of associating a frame with a lattice.
(Joint work with Prof Ewa Orlowska, National Institute of Telecommunications in Warsaw, funded by the NRF and SA-Poland bilateral cooperation.)