Cristian S. Calude

In this paper we consider the possibility of a Quantum Molinism : such a view applies an analogue of the Molinistic account of free will‘s compatibility with God’s foreknowledge to God’s knowledge of (supposedly) indeterministic events at a quantum level. W e ask how (and why) a providential God could care for and know about a world with this kind of indeterminacy. We consider various formulations of such a Quantum Molinism, and after rejecting a number of options arrive at one seemingly coherent formulation.

We prove that every computably enumerable random real is provable in Peano Arithmetic to be c.e. random. A major step in the proof is to show that the theorem stating that “a real is c.e. and random iff it is the halting probability of a universal prefix-free Turing machine” can be proven in PA. Our proof, which is simpler than the standard one, can also be used for the original theorem. Our positive result can be contrasted with the case of computable functions, where not every computable function is provably computable in PA, or even more interestingly, with the fact that almost all random finite strings are not provably random in PA. We also prove two negative results: a) there exists a universal machine whose universality cannot be proved in PA, b) there exists a universal machine U such that, based on U, PA cannot prove the randomness of its halting probability. The paper also includes a sharper form of the Kraft-Chaitin Theorem, as well as a formal proof of this theorem written with the proof assistant Isabelle

Finite automata have been recently used as alternative, discrete models in theoretical physics, especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/ extrinsic perception . These studies deal with Moore experiments; the main result states that it is impossible to determine the initial state of an automaton, and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For this aim the classical theory of finite automata — which considers automata with initial states — is not adequate, and a new approach is necessary. A study of finite deterministic automata without initial states is exactly the aim of this paper. We will define and investigate the complexity of various types of simulations between automata. Minimal automata will be constructed and proven to be unique up to an isomorphism. We will build our results on an extension of Myhill-Nerode technique; all constructions will make use of “automata responses” to simple experiments only, i.e., no information about the internal machinery will be considered available.

This volume contains the papers presented at the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS1), which was held at 'Ovidius'University Constantza, Romania in July 2001. The conference was open to all areas of discrete mathematics and theoretical computer science, and the papers contained within this volume cover topics such as: abstract data types and specifications; algorithms and data structures; automata and formal languages; computability, complexity and constructive mathematics; discrete mathematics, combinatorial computing and category theory; logic, nonmonotonic logic and hybrid systems; molecular computing.

The fourthDiscrete Mathematics andTheoreticalComputer Science Conference was jointly organized by the Centre for Discrete Mathematics and Theoretical Computer Science of the University of Auckland and the University of Bourgogne in Dijon, France, and took place in Dijon from 7 to12 July2003.Thepreviousconferenceswereheld inAuckland,NewZealand and Constan ̧ ta, Romania. The?ve invited speakers of the conference were: G.J. Chaitin, C. Ding, S. Istrail, M. Margenstein, and T. Walsh. The Programme Committee, consisting of V. Berthe, S. Boza- lidis,C.S.Calude,V.E.Cazanescu, F. Cucker, M. Deza, J. Diaz, M.J. D- neen,B.Durand,L.Hemaspaandra, P. Hertling, J. Kohlas, G. Markowski, M. Mitrovic, A. Salomaa, L. Staiger, D. Skordev, G. Slutzki, I. Tomescu, M. Yasugi, and V. Vajnovszki, selected 18 papers to be presented as regular contributions and 1 5 other special CDMTCS papers.

We study some aspects of the emergence of _lógos_ from _xáos_ on a basal model of the universe using methods and techniques from algorithmic information and Ramsey theories. Thereby an intrinsic and unusual mixture of meaningful and spurious, emerging laws surfaces. The spurious, emergent laws abound, they can be found almost everywhere. In accord with the ancient Greek theogony one could say that _lógos_, the Gods and the laws of the universe, originate from “the void,„ or from _xáos_, a picture which supports the unresolvable/irreducible lawless hypothesis. The analysis presented in this paper suggests that the “laws„ discovered in science correspond merely to syntactical correlations, are local and not universal.

Very large databases are a major opportunity for science and data analytics is a remarkable new field of investigation in computer science. The effectiveness of these tools is used to support a “philosophy” against the scientific method as developed throughout history. According to this view, computer-discovered correlations should replace understanding and guide prediction and action. Consequently, there will be no need to give scientific meaning to phenomena, by proposing, say, causal relations, since regularities in very large databases are enough: “with enough data, the numbers speak for themselves”. The “end of science” is proclaimed. Using classical results from ergodic theory, Ramsey theory and algorithmic information theory, we show that this “philosophy” is wrong. For example, we prove that very large databases have to contain arbitrary correlations. These correlations appear only due to the size, not the nature, of data. They can be found in “randomly” generated, large enough databases, which—as we will prove—implies that most correlations are spurious. Too much information tends to behave like very little information. The scientific method can be enriched by computer mining in immense databases, but not replaced by it.

In a famous lecture in 1900, David Hilbert listed 23 difficult problems he felt deserved the attention of mathematicians in the coming century. His conviction of the solvability of every mathematical problem was a powerful incentive to future generations: ``Wir müssen wissen. Wir werden wissen.'' (We must know. We will know.) Some of these problems were solved quickly, others might never be completed, but all have influenced mathematics. Later, Hilbert highlighted the need to clarify the methods of mathematical reasoning, using a formal system of explicit assumptions, or axioms. Hilbert's vision was the culmination of 2,000 years of mathematics going back to Euclidean geometry. He stipulated that such a formal axiomatic system should be both `consistent' (free of contradictions) and `complete' (in that it represents all the truth). Hilbert also argued that any wellposed mathematical problem should be `decidable', in the sense that there exists a mechanical procedure, a computer program, for deciding whether something is true or not. Of course, the only problem with this inspiring project is that it turned out to be impossible.

Turing’s famous 1936 paper “On computable numbers, with an application to the Entscheidungsproblem” defines a computable real number and uses Cantor’s diagonal argument to exhibit an uncomputable real. Roughly speaking, a computable real is one that one can calculate digit by digit, that there is an algorithm for approximating as closely as one may wish. All the reals one normally encounters in analysis are computable, like π, √2 and e. But they are much scarcer than the uncomputable reals because, as Turing points out, the computable reals are countable, whilst the uncomputable reals have the power of the continuum. Furthermore, any countable set of reals has measure zero, so the computable reals have measure zero. In other words, if one picks a real at random in the unit interval with uniform probability distribution, the probability of obtaining an uncomputable real is unity. One may obtain a computable real, but that is in- finitely improbable. But how about individual examples of uncomputable reals? We will show two: H and the halting probability Ω, both contained in the unit interval. Their construction was anticipated in..

Penrose [40] has discussed a new point of view concerning the nature of physics that might underline conscious thought processes. He has argued that it might be the case that some physical laws are not computable, i.e. they cannot be properly simulated by computer; such laws can most probably arise on the “no-man’s-land” between classical and quantum physics. Furthermore, conscious thinking is a non-algorithmic activity. He is opposing both strong AI , and Searle’s [47] contrary viewpoint mathematical “laws”)

Suppose that persons A and B give us a sequence of 32 bits each, saying that they were obtained from independent coin flips. If A gives the stringu = 01001110100111101001101001110101and B gives the stringv = 00000000000000000000000000000000,then we would tend to believe A and would not believe B: the string u seems to be random, but the string v does not. Further on, if we change the value of a bit in a “random” string, then the result is still a “random” string. If we keep making such changes in a “random” string, then we will eventually complete destroy randomness