91 results for Calude, C.S, Report

  • De-Quantising the Solution of Deutsch's Prolem

    Calude, C.S (2006-08)

    Report
    The University of Auckland Library

    Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch’s problem. Consider a Boolean function f : {0,1}→{0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant (that is, f (0) = f (1)) or balanced ( f (0) ≠ f (1)). Classically, to solve the problem seems to require the computation of f (0) and f (1), and then the comparison of results. Is it possible to solve the problem with only one query on f ? In a famous paper published in 1985, Deutsch posed the problem and obtained a “quantum” partial affirmative answer. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be de-quantised to a deterministic simpler solution which is as efficient as the quantum one. The use of “superposition”, a key ingredient of quantum algorithm, is—in this specific case—classically available.

    View record details
  • Degree-Theoretic Aspects of Computably Enumerable Reals

    Calude, C.S; Coles, R.J; Hertling, P.H; Khoussainov, B (1998-09)

    Report
    The University of Auckland Library

    A real α is computable if its left cut, L(α); is computable. If (qi)i is a computable sequence of rationals computably converging to α, then {qi}, the corresponding set, is always computable. A computably enumerable (c.e.) real is a real which is the limit of an increasing computable sequence of rationals, and has a left cut which is c.e. We study the Turing degrees of representations of c.e. reals, that is the degrees of increasing computable sequences converging to α. For example, every representation A of α is Turing reducible to L(α). Every noncomputable c.e. real has both a computable and noncomputable representation. In fact, the representations of noncomputable c.e. re- als are dense in the c.e. Turing degrees, and yet not every c.e. Turing degree below degT L(α) necessarily contains a representation of α.

    View record details
  • A Genius' Story: Two Books on Godel

    Calude, C.S (1997-06)

    Report
    The University of Auckland Library

    Undoubtly, Gödel was the greatest logician of the twentieth century. There is no trace of exaggeration in saying, following Wang, that Gödel's contribution to mathematics has the same status as Freudian psychology, Einstein's theory of relativity, Bohr's principle of complementarity, Heisenberg's uncertainty principle, keynesian economics, and Watson and Crick double helix model of DNA. Yet, with a few notable exceptions, most of the personal details of Gödel's life remained a mystery

    View record details
  • Is Complexity a Source of Incompleteness?

    Calude, C.S; Juergensen, H (2004-06)

    Report
    The University of Auckland Library

    In this paper we prove Chaitin’s “heuristic principle”, the theorems of a finitelyspecified theory cannot be significantly more complex than the theory itself, for an appropriate measure of complexity. We show that the measure is invariant under the change of the G¨odel 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.

    View record details
  • Solving Problems with Finite Test Sets

    Calude, C.S; Juergensen, H; Legg, S (1999-09)

    Report
    The University of Auckland Library

    Every finite and every co-finite set of non-negative integers is decidable. This is true and it is not, depending on whether the set is given constructively. A similar constraint is applicable in language theory and many other fields. The constraint is usually understood and, hence, omitted. The phenomenon of a set being finite, but possibly undecidable, is, of course, a consequence of allowing non-constructive arguments in proofs. In this note we discuss a few ramifications of this fact. We start out with showing that every number theoretic statement that can be expressed in first-order logic can be reduced to a finite set, to be called a test set. Thus, if one knew the test set, one could determine the truth of the statement. The crucial point is, of course, that we may not able to know what the finite test set is. Using problems in the class II1 of the arithmetic hierarchy as an example, we establish that the bound on the size of the test set is Turing-complete and that it is upper-bounded by the busy-beaver function. This re-enforces the fact that there is a vast difference between finiteness and constructive finiteness. In the context of the present re-opened discussion about the notion of computability – possibly extending its realm through new computational models derived from physics – the constraint of constructivity of the model itself may add another twist.

    View record details
  • Proving as a Computable Procedure

    Calude, C.S; Rudeanu, S (2004-10)

    Report
    The University of Auckland Library

    Gödel’s incompleteness theorem states that every finitely-presented, 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 computer-assisted 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 Church-Turing thesis.

    View record details
  • Who Is Afraid of Randomness?

    Calude, C.S (2000-09)

    Report
    The University of Auckland Library

    Randomness–the mark of anxiety, the cause of disarray or misfortune, the cure for boring repetitiveness, is, like it or not, one of the most powerful driving forces of life. Is it bad? Is it good? The struggle with uncertainty and risk caused by natural disasters, market downturns or terrorism is balanced by the role played by randomness in generating diversity and innovation, in allowing complicated structures to emerge through the exploitation of serendipitous accidents. To many minds any discussion about randomness is purely academic, just another mathematical or philosophical pedantry. False! Randomness could be a matter of life or death, as in the case of Sudden Infant Death Syndrome (SIDS), a merciless child-killer. The present paper describes some difficulties regarding the mathematical modelling of randomness, contrasts silicon-computer generated pseudorandom bits with quantum-computer “random” bits, succinctly presents the algorithmic definition of randomness proposed by algorithmic information theory and the relations between randomness and (logical) incompleteness, briefly presents some applications of algorithmic randomness in physics and finishes by advocating “experimental mathematics”, a quasiempirical, more pragmatic manner view of mathematics.

    View record details
  • From Heisenberg to Goedel via Chaitin

    Calude, C.S; Stay, M.A (2004-02)

    Report
    The University of Auckland Library

    In 1927 Heisenberg discovered that the “more precisely the position is determined, the less precisely the momentum is known in this instant, and vice versa”. Four years later Gödel showed that a finitely specified, consistent formal system which is large enough to include arithmetic is incomplete. As both results express some kind of impossibility it is natural to ask whether there is any relation between them, and, indeed, this question has been repeatedly asked for a long time. The main interest seems to have been in possible implications of incompleteness to physics. In this note we will take interest in the converse implication and will offer a positive answer to the question: Does uncertainty imply incompleteness? We will show that algorithmic randomness is equivalent to a “formal uncertainty principle” which implies Chaitin’s information-theoretic incompleteness. We also show that the derived uncertainty relation, for many computers, is physical. In fact, the formal uncertainty principle applies to all systems governed by the wave equation, not just quantum waves. This fact supports the conjecture that uncertainty implies algorithmic randomness not only in mathematics, but also in physics.

    View record details
  • Supplemental Papers for the 2nd Unconventional Models of Computation Conference

    Antoniou, I; Calude, C.S; Dinneen, M.J (2000-11)

    Report
    The University of Auckland Library

    These are additional papers of talks that were presented at the Second International Conference on Unconventional Models of Computation (UMC’2K). UMC’2K, organized by the Centre for Discrete Mathematics and Theoretical Computer Science, the International Solvay Institutes for Physics and Chemistry and the Vrije Universiteit Brussel Theoretical Physics Division was held at Solvay Institutes during December 13–16, 2000. The conference encompasses all areas of unconventional computation, especially quantum computing, DNA-based computation, evolutionary algorithms and other proposals for computation models that go beyond the Turing model. Additional refereed and invited papers of UMC’2K appear in the following proceedings: I. Antoniou, C. S. Calude, M. J. Dinneen, editors. Unconventional Models of Computation, UMC’2K, Springer-Verlag, London, December 2000, XI + 301 pages.

    View record details
  • Is there a Universal Image Generator

    Calude, C.S; Lewis, J.P (2009-01)

    Report
    The University of Auckland Library

    Synthetic pattern generation procedures have various applications, and a number of approaches (fractals, L-systems, etc.) have been devised. A fundamental underlying question is: will new pattern generation algorithms continue to be invented, or is there some “universal” algorithm that can generate all (and only) the perceptually distinguishable images, or even all members of a restricted class of patterns such as logos or letterforms? In fact there are many complete algorithms that can generate all possible images, but most images are random and not perceptually distinguishable. Counting arguments show that the percentage of distinguishable images that will be generated by such complete algorithms is vanishingly small. In this paper we observe that perceptually distinguishable images are compressible. Using this observation it is evident that algorithmic complexity provides an appropriate framework for discussing the question of a universal image generator. We propose a natural Thesis for describing perceptually distinguishable images and argue its validity. Based on it, we show that there is no program that generates all (and only) these images. Although this is an abstract result, it may have import for several areas in graphics that deal with compressible signals. In essence, new representations and pattern generation algorithms will continue to be developed; there is no feasible “super algorithm” that is capable of all things.

    View record details
  • Supplemental Abstracts for DMTCS01

    Calude, C.S; Dinneen, Michael; Sburlan, S (2001-04)

    Report
    The University of Auckland Library

    These 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 2-6. 2001.

    View record details
  • A Dialogue on the Internet

    Calude, C.S; Carpenter, B. E (2008-04)

    Report
    The University of Auckland Library

    Dr. Brian E. Carpenter is a distinguished computer scientist and engineer working on Internet standards and technology. The University of Auckland was privileged to attract Brian in 2007; before coming to Auckland, he led the networking group at CERN, the European Laboratory for Particle Physics, and worked for IBM as a Distinguished Engineer. Brian chaired the Internet Architecture Board, the Internet Engineering Task Force, and served as a trustee of the Internet Society. Brian was heavily involved in the design and deployment of IPv6. He is also interested in Internet quality of service and measurement issues. Brian was a member of the IBM Academy of Technology (membership lapses when one leaves IBM).

    View record details
  • Bisimulations and Behaviour of Nondeterministic Automata

    Calude, C.S; Calude, E (1999-02)

    Report
    The University of Auckland Library

    The minimization of nondeterministic automata without initial states (developed within a game-theoretic 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
  • Counterfactual Effect, the Halting Problem, and the Busy Beaver Function

    Calude, C.S; Dinneen, Michael; Svozil, K (1999-07)

    Report
    The University of Auckland Library

    Using the counterfactual effect, we demonstrate that with better than 50% chance we can determine whether an arbitrary universal Turing machine will halt on an arbitrarily given program. As an application we indicate a probabilistic method for computing the busy beaver function| a classical uncomputable function. These results suggest a possibility of going beyond the Turing barrier.

    View record details
  • A Characterization of C.E. Random Reals

    Calude, C.S (1999-03)

    Report
    The University of Auckland Library

    A real α is computably enumerable if it is the limit of a computable, increasing, converging sequence of rationals; α is random if its binary expansion is a random sequence. Our aim is to offer a self-contained proof, based on the papers [7, 14, 4, 13], of the following theorem: a real is c.e. and random if and only if it a Chaitin Ω real, i.e., the halting probability of some universal self-delimiting Turing machine.

    View record details
  • Metric Lexical Analysis

    Calude, C.S; Salomaa, K; Yu, S (1999-03)

    Report
    The University of Auckland Library

    We study automata-theoretic properties of distances and quasi-distances between words. We show that every additive distance is finite. We also show that every additive quasi-distance is regularity-preserving, that is, the neighborhood of any radius of a regular language with respect to an additive quasi distance is regular. As an application we present a simple algorithm that constructs a metric (fault-tolerant) lexical analyzer for any given lexical analyzer and desired radius (fault-tolerance index).

    View record details
  • The Poincare-Hardy Inequality on the Complement of a Cantor Set

    Calude, C.S; Pavlov, B (2000-05)

    Report
    The University of Auckland Library

    The Poincaré–Hardy inequality [see pdf for formula] is derived in R3 on the complement of a Cantor set E. We use a special self-similar tiling and a natural metric on the space of trajectories generated by a Mauldin–Williams graph which is homeomorphic with the space of tiles endowed with the Euclidean distance. A crude estimation of the constant K2 is 2,100. Two applications will be briefly discussed. In the last one, the constant K−1 ≈ 0.021819 plays the role of an estimate for the dimensionless Plank constant in the corresponding uncertainty principle.

    View record details
  • Exact Approximations of Omega Numbers

    Calude, C.S; Dinneen, Michael (2006-12)

    Report
    The University of Auckland Library

    A Chaitin Omega number is the halting probability of a universal prefix-free Turing machine. Every Omega number is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable. The value of an Omega number is highly machine-dependent. In general, no more than finitely many scattered bits of the binary expansion of an Omega number can be exactly computed; but, in some cases, it is possible to prove that no bit can be computed. In this paper we will simplify and improve both the method and its correctness proof proposed in an earlier paper, and we will compute the exact approximations of two Omega numbers of the same prefix-free Turing machine, which is universal when used with data in base 16 or base 2: we compute 43 exact bits for the base 16 machine and 40 exact bits for the base 2 machine.

    View record details
  • Breaking the Turing Barrier

    Calude, C.S; Dinneen, Michael (1998-05)

    Report
    The University of Auckland Library

    Is there any limit to discrete computation, and more generally, to scientific knowledge? This is one of the problems studied by the Centre for Discrete Mathematics and Theoretical Computer Science of the University of Auckland.

    View record details
  • Simplicity via Provability for Universal Prefix-free Turing Machines

    Calude, C.S (2008-11)

    Report
    The University of Auckland Library

    Universality is one of the most important ideas in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we review recent results in Algorithmic Information Theory and propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, PA or ZFC. In all cases some, but not all, machines are simple.

    View record details