91 results for Calude, C.S, Report

DeQuantising the Solution of Deutsch's Prolem
Calude, C.S (200608)
Report
The University of Auckland LibraryProbably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the socalled 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, probabilityone solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be dequantised 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 
DegreeTheoretic Aspects of Computably Enumerable Reals
Calude, C.S; Coles, R.J; Hertling, P.H; Khoussainov, B (199809)
Report
The University of Auckland LibraryA 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 (199706)
Report
The University of Auckland LibraryUndoubtly, 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 (200406)
Report
The University of Auckland LibraryIn 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 finitelyspecified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like ZermeloFraenkel 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 (199909)
Report
The University of Auckland LibraryEvery finite and every cofinite set of nonnegative 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 nonconstructive 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 firstorder 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 Turingcomplete and that it is upperbounded by the busybeaver function. This reenforces the fact that there is a vast difference between finiteness and constructive finiteness. In the context of the present reopened 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 (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 
Who Is Afraid of Randomness?
Calude, C.S (200009)
Report
The University of Auckland LibraryRandomness–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 childkiller. The present paper describes some difficulties regarding the mathematical modelling of randomness, contrasts siliconcomputer generated pseudorandom bits with quantumcomputer “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 (200402)
Report
The University of Auckland LibraryIn 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 informationtheoretic 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 (200011)
Report
The University of Auckland LibraryThese 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, DNAbased 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, SpringerVerlag, London, December 2000, XI + 301 pages.
View record details 
Is there a Universal Image Generator
Calude, C.S; Lewis, J.P (200901)
Report
The University of Auckland LibrarySynthetic pattern generation procedures have various applications, and a number of approaches (fractals, Lsystems, 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 (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 
A Dialogue on the Internet
Calude, C.S; Carpenter, B. E (200804)
Report
The University of Auckland LibraryDr. 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 (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 
Counterfactual Effect, the Halting Problem, and the Busy Beaver Function
Calude, C.S; Dinneen, Michael; Svozil, K (199907)
Report
The University of Auckland LibraryUsing 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 (199903)
Report
The University of Auckland LibraryA 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 selfcontained 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 selfdelimiting Turing machine.
View record details 
Metric Lexical Analysis
Calude, C.S; Salomaa, K; Yu, S (199903)
Report
The University of Auckland LibraryWe study automatatheoretic properties of distances and quasidistances between words. We show that every additive distance is finite. We also show that every additive quasidistance is regularitypreserving, 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 (faulttolerant) lexical analyzer for any given lexical analyzer and desired radius (faulttolerance index).
View record details 
The PoincareHardy Inequality on the Complement of a Cantor Set
Calude, C.S; Pavlov, B (200005)
Report
The University of Auckland LibraryThe Poincaré–Hardy inequality [see pdf for formula] is derived in R3 on the complement of a Cantor set E. We use a special selfsimilar 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 (200612)
Report
The University of Auckland LibraryA Chaitin Omega number is the halting probability of a universal prefixfree 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 machinedependent. 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 prefixfree 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 (199805)
Report
The University of Auckland LibraryIs 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 Prefixfree Turing Machines
Calude, C.S (200811)
Report
The University of Auckland LibraryUniversality 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 prefixfree 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