91 results for Calude, C.S, Report

Dialogues on Quantum Computing
Calude, C.S (200306)
Report
The University of Auckland LibraryWhat sort of machines do useful computation in a universe described by classical mechanics? The answer was provided in 1936 by the British mathematician Alan Turing, and it’s known today as the Turing machine. But even in 1936 classical mechanics was known to be false, and so one could have asked the question: What sort of machines do useful computation in a universe described by quantum mechanics? In a trivial sense, everything is a quantum computer. A pebble is a quantum computer for calculating the constantposition function; current computers exploit quantum effects (like electrons tunneling through barriers) to control computation and to be able to run fast. But quantum computing is much more than that. In what follows we will present – in the form of a biased, informal dialogue – a few keyideas on quantum computing.
View record details 
Quantum Randomness and Value Indefiniteness
Calude, C.S; Svozil, K (200611)
Report
The University of Auckland LibraryAs computability implies value definiteness, certain sequences of quantum outcomes cannot be computable.
View record details 
Most Short Programs Halt Quickly or Never Halt
Calude, C.S; Stay, M.A (200608)
Report
The University of Auckland LibraryThe aim of this paper is to provide a probabilistic, but nonquantum, analysis of the Halting Problem. Our approach is to have the probability space extend over both space and time and to consider the probability that a random Nbit program has halted by a random time. We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer k > 0, we can effectively compute a time bound T such that the probability that an Nbit program will eventually halt given that it has not halted by T is smaller than 2−k. We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that “long” runtimes are effectively rare. More formally, the set of times at which an Nbit program can stop after the time 2N+constant has effectively zero density.
View record details 
Supplemental Abstracts for DMTCS01
Calude, C.S; Dinneen, Michael; Sburlan, S (200104)
Report
The University of Auckland LibraryThese are the abstracts of the poster talks to be given at the 3rd International Conference Discrete Mathematics and Theoretical Computer Science, 2001, to be held at the ‘Ovidus’ University, Constanta, Romania, on July 26. 2001.
View record details 
Embedding Quantum Universes into Classical Ones
Calude, C.S; Hertling, P.H; Svozil, K (199705)
Report
The University of Auckland LibraryDo the partial order and lattice operations of a quantum logic correspond to the logical implication and connectives of classical logic? Rephrased, how far might a classical understanding of quantum mechanics be, in principle, possible? A celebrated result by Kochen and Specker answers the above question in the negative. However, this answer is just one among different possible ones, not all negative. It is our aim to discuss the above question in terms of mappings of quantum worlds into classical ones, more specifically, in terms of embeddings of quantum logics into classical logics; depending upon the type of restrictions imposed on embeddings the question may get negative or positive answers.
View record details 
Computing with Cells and Atoms: After Five Years
Calude, C.S; Paun, G (200408)
Report
The University of Auckland LibraryThis is the text added to the Russian edition of our book Computing with Cells and Atoms (Taylor & Francis Publishers, London, 2001) to be published by Pushchino Publishing House. The translation was done by Professor Victor Vladimirovich Ivanov and Professor Robert Polozov.
View record details 
A Glimpse into Natural Computing
Calude, C.S; Paun, G; Tataram, Monica (199912)
Report
The University of Auckland LibraryWe consider as pertaining to Natural Computing (in some sense, characterizing it) the following five domains: Neural Networks, Genetic Algorithms, DNA Computing, Membrane Computing, and Quantum Computing. The first two domains are well established, the last three are just now looking for a place in the toolkit of practitioners. Here, we briefly introduce the last three domains to the reader. The main point is that in all these areas one aims at solving intractable (NPcomplete) problems in polynomial (in many cases, even linear) time. Taking into account that most significant practical problems (optimization, scheduling, programming, combinatorial, etc.) are intractable, it follows that the promises of Natural Computing should be taken seriously.
View record details 
A New Measure of the Difficulty of Problems
Calude, C.S; Calude, E; Dinneen, Michael (200602)
Report
The University of Auckland LibraryGuessing the degree of difficulty of a problem before seeing its solution is notoriously hard not only for beginners, but also for the most experienced professionals. Can we develop a method to evaluate, in some objective way, the difficulty of an open problem? This note proposes such a measure which can be used for a fairly large class of finitely refutable conjectures which includes, for example, Riemann Hypothesis and the Goldbach’s Conjecture. According to our measure, Riemann Hypothesis is more complex than Goldbach’s Conjecture. We also show, in a nonconstructive way, that the Collatz 3x+1 Problem is finitely refutable; consequently, our method cannot be applied, hence stronger versions of this problem are studied.
View record details 
Passages of Proof
Calude, C.S; Calude, E; Marcus, S (200202)
Report
The University of Auckland LibraryIn this paper we propose a new perspective on the evolution and history of the idea of mathematical proof. Proofs will be studied at three levels: syntactical, semantical and pragmatical. Computerassisted proofs will be give a special attention. Finally, in a highly speculative part, we will anticipate the evolution of proofs under the assumption that the quantum computer will materialize. We will argue that there is little ‘intrinsic’ difference between traditional and ‘unconventional’ types of proofs.
View record details 
Disjunctive Sequences: An Overview
Calude, C.S; Priese, L; Staiger, L (199710)
Report
The University of Auckland LibraryFollowing Jürgensen and Thierrin [21] we say that an infinite sequence is disjunctive if it contains any (finite) word, or, equivalently, if any word appears in the sequence infinitely many times. “Disjunctivity” is a natural qualitative property; it is weaker, than the property of “normality” (introduced by Borel [1]; see, for instance, Kuipers, Niederreiter [24]). The aim of this paper is to survey some basic results on disjunctive sequences and to explore their role in various areas of mathematics (e.g. in automatatheoretic studies of ωlanguages or number theory). To achieve our goal we will use various instruments borrowed from topology, measuretheory, probability theory, number theory, automata and formal languages.
View record details 
Generalisations of Disjunctive Sequences
Calude, C.S; Staiger, L (200306)
Report
The University of Auckland LibraryThe present paper proposes a generalisation of the notion of disjunctive (or rich) sequence, that is, of an infinite sequence of letters having each finite sequence as a subword. Our aim is to give a reasonable notion of disjunctiveness relative to a given set of sequences F. We show that a definition like “every subword which occurs at infinitely many different positions in sequences in F has to occur infinitely often in the sequence” fulfils properties similar to the original unrelativised notion of disjunctiveness. Finally, we investigate our concept of generalised disjunctiveness in spaces of Cantor expansions of reals.
View record details 
Computational Complementarity and Sofic Shifts
Calude, C.S; Lipponen, M (199708)
Report
The University of Auckland LibraryFinite automata (with outputs but no initial states) have been extensively used as models of computational complementarity, a property which mimics the physical complementarity. All this work was focussed on “frames", i.e., on fixed, static, local descriptions of the system behaviour. In this paper we are mainly interested in the asymptotical description of complementarity. To this aim we will study the asymptotical behaviour of two complementarity principles by associating to every incomplete deterministic automaton (with outputs, but no initial state) certain sofic shifts: automata having the same behaviour correspond to a unique sofic shift. In this way, a class of sofic shifts reflecting complementarity will be introduced and studied. We will prove that there is a strong relation between “local complementarity", as it is perceived at the level of “frames", and “asymptotical complementarity" as it is described by the sofic shift.
View record details 
Real Numbers: From Computable to Random
Calude, C.S (200008)
Report
The University of Auckland LibraryA real is computable if it is the limit of a computable, increasing, computably converging sequence of rationals. Omitting the restriction that the sequence converges computably we arrive at the notion of computably enumerable (c.e.) real, that is, the limit of a computable, increasing, converging sequence of rationals. A real is random if its binary expansion is a random sequence (equivalently, if its expansion in base b ≥ 2 is random). The aim of this paper is to review some recent results on computable, c.e. and random reals. In particular, we will present a complete characterization of the class of c.e. and random reals in terms of halting probabilities of universal Chaitin machines, and we will show that every c.e. and random real is the halting probability of some Solovay machine, that is, a universal Chaitin machine for which ZFC (if sound) cannot determine more than its initial block of 1 bits. A few open problems will be also discussed.
View record details 
Proving as a Computable Procedure
Calude, C.S; Rudeanu, S (200410)
Report
The University of Auckland LibraryGödel’s incompleteness theorem states that every finitelypresented, consistent, sound theory which is strong enough to include arithmetic is incomplete. In this paper we present elementary proofs for three axiomatic variants of Gödel’s incompleteness theorem and we use them (a) to illustrate the idea that there is more than “complete vs. incomplete”, there are degrees of incompleteness, and (b) to discuss the implications of incompleteness and computerassisted proofs for Hilbert’s Programme. We argue that the impossibility of carrying out Hilbert’s Programme is a thesis and has a similar status to the ChurchTuring thesis.
View record details 
Natural Halting Probabilities, Partial Randomness, and Zeta Functions
Calude, C.S; Stay, M.A (200511)
Report
The University of Auckland LibraryWe introduce the zeta number, natural halting probability and natural complexity of a Turing machine and we relate them to Chaitin’s Omega number, halting probability, and programsize complexity. A classification of Turing machines according to their zeta numbers is proposed: divergent, convergent and tuatara. We prove the existence of universal convergent and tuatara machines. Various results on (algorithmic) randomness and partial randomness are proved. For example, we show that the zeta number of a universal tuatara machine is c.e. and random. A new type of partial randomness, asymptotic randomness, is introduced. Finally we show that in contrast to classical (algorithmic) randomness—which cannot be naturally characterised in terms of plain complexity—asymptotic randomness admits such a characterisation.
View record details 
Bisimulations and Behaviour of Nondeterministic Automata
Calude, C.S; Calude, E (199902)
Report
The University of Auckland LibraryThe minimization of nondeterministic automata without initial states (developed within a gametheoretic framework in Calude, Calude, Khoussainov [3]) is presented in terms of bisimulations; the minimal automaton is unique up to an isomorphism in case of reversible automata. We also prove that there exists an in nite class of (strongly connected) nondeterministic automata each of which is not bisimilar with any deterministic automaton. This shows that in the sense of bisimilarity nondeterministic automata are more powerful than deterministic ones. It is an open question whether the method of bisimulations can produced, in general, the unique minimal nondeterministic automaton.
View record details 
Every Computably Enumerable Random Real Is Provably Computably Enumerable Random
Calude, C.S; Hay, N.J (200807)
Report
The University of Auckland LibraryWe prove that every computably enumerable (c.e.) random real is provable in Peano Arithmetic (PA) to be c.e. random, a statement communicated to one author by B. Solovay. 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 prefixfree Turing machine" can be proven in PA. Our proof, which is simpler than the standard one, can also be used for the original theorem. The result that every c.e. random real is provably c.e. random is in contrast with the case of computable functions, where not every computable function is provably computable. It is even more interesting to compare this result with the fact that – in general – random finite strings are not provably random. The paper also includes a sharper form of the KraftChaitin Theorem, as well as an automatic proof of this theorem written with the interactive theorem prover Isabelle.
View record details 
Entropic Measures, Markov Information Sources and Complexity
Calude, C.S; Dumitrescu, M (200102)
Report
The University of Auckland LibraryThe concept of entropy plays a major part in communication theory. The Shannon entropy is a measure of uncertainty with respect to a priori probability distribution. In algorithmic information theory the information content of a message is measured in terms of the size in bits of the smallest program for computing that message. This paper discusses the classical entropy and entropy rate for discrete or continuous Markov sources, with finite or continuous alphabets, and their relations to programsize complexity and algorithmic probability. The accent is on ideas, constructions and results; no proofs will be given.
View record details 
Recursively Enumerable Reals and Chaitin Omega Numbers
Calude, C.S; Hertling, P.H; Khoussainov, B; Wang, Y (199710)
Report
The University of Auckland LibraryA real α is called recursively enumerable if it can be approximated by an increasing, recursive sequence of rationals. The halting probability of a universal self delimiting Turing machine (Chaitin's Ω number, [10]) is a random r.e. real. Solovay's [25] Ωlike reals are also random r.e. reals. Solovay showed that any Chaitin Ω number is Ωlike. In this paper we show that the converse implication is true as well: any Ωlike real in the unit interval is the halting probability of a universal selfdelimiting Turing machine. Following Solovay [25] and Chaitin [11] we say that an r.e. real α dominates an r.e. real β if from a good approximation of α from below one can compute a good approximation of β from below. We shall study this relation and characterize it in terms of relations between r.e. sets. Ωlike numbers are the maximal r.e. real numbers with respect to this order, that is, from a good approximation to an Ωlike real one can compute a good approximation for every r.e. real. This property shows the strength of Ω for approximation purposes. However, the situation is radically different if one wishes to compute digits of the binary expansion of an r.e. real: one cannot compute with a total recursive function the first n digits of the r.e. real 0:¬xK (the characteristic sequence of the halting problem) from the first g(n) digits of Ω, for any total recursive function g.
View record details 
Mathematical Proofs at a Crossroad?
Calude, C.S; Marcus, S (200403)
Report
The University of Auckland LibraryFor more than 2000 years, from Pythagoras and Euclid to Hilbert and Bourbaki, mathematical proofs were essentially based on axiomaticdeductive reasoning. In the last decades, the increasing length and complexity of many mathematical proofs led to the expansion of some empirical, experimental, psychological and social aspects, yesterday only marginal, but now changing radically the very essence of proof. In this paper, we try to organize this evolution, to distinguish its different steps and aspects, and to evaluate its advantages and shortcomings. Axiomaticdeductive proofs are not a posteriori work, a luxury we can marginalize nor are computerassisted proofs bad mathematics. There is hope for integration!
View record details