91 results for Calude, C.S, Report

  • 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
  • Incompleteness, Complexity, Randomness and Beyond

    Calude, C.S (2001-11)

    Report
    The University of Auckland Library

    Gödel’s Incompleteness Theorems have the same scientific status as Einstein’s principle of relativity, Heisenberg’s uncertainty principle, and Watson and Crick’s double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.

    View record details
  • A Glimpse into Natural Computing

    Calude, C.S; Paun, G; Tataram, Monica (1999-12)

    Report
    The University of Auckland Library

    We 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 (NP-complete) 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
  • Randomness Relative to Cantor Expansions

    Calude, C.S; Staiger, L; Svozil, K (2003-04)

    Report
    The University of Auckland Library

    Imagine a sequence in which the first letter comes from a binary alphabet, the second letter can be chosen on an alphabet with 10 elements, the third letter can be chosen on an alphabet with 3 elements and so on. Such sequences occur in various physical contexts, in which the coding of experimental outcome varies with scale. When can such a sequence be called random? In this paper we offer a solution to the above question using the approach to randomness proposed by Algorithmic Information Theory.

    View record details
  • Proving and Programming

    Calude, C.S; Calude, E; Marcus, S (2007-06)

    Report
    The University of Auckland Library

    There is a strong analogy between proving theorems in mathematics and writing programs in computer science. This paper is devoted to an analysis, from the perspective of this analogy, of proof in mathematics. We will argue that while the Hilbertian notion of proof has few chances to change, future proofs will be of various types, will play different roles, and their truth will be checked differently. Programming gives mathematics a new form of understanding. The computer is the driving force behind these changes.

    View record details
  • A Glimpse into Algorithmic Information Theory

    Calude, C.S (1999-02)

    Report
    The University of Auckland Library

    This paper is a subjective, short overview of algorithmic information theory. We critically discuss various equivalent algorithmical models of randomness motivating a "randomness hypothesis". Finally some recent results on computably enumerable random reals are reviewed.

    View record details
  • Computational Complementarity and Sofic Shifts

    Calude, C.S; Lipponen, M (1997-08)

    Report
    The University of Auckland Library

    Finite 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 (2000-08)

    Report
    The University of Auckland Library

    A 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
  • A New Measure of the Difficulty of Problems

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

    Report
    The University of Auckland Library

    Guessing 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
  • Pre-proceedings of the Workshop Physics and Computation

    Calude, C.S; Costa, J.F (2008 -07)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Workshop on Truths and Proofs

    Bridges, D.S; Calude, C.S; Kroon, F (2001-11)

    Report
    The University of Auckland Library

    The Workshop is part of the Australasian Association of Philosophy (New Zealand Division) Annual Conference to be held in Auckland, New Zealand on 2-7 December 2001. The Workshop consists of seven talks and one roundtable discussion. The programme, including the abstracts of talks, follows.

    View record details
  • Chaitin Omega Numbers and Strong Reducibilities

    Calude, C.S; Nies, A (1997-10)

    Report
    The University of Auckland Library

    We prove that any Chaitin Ω number (i.e., the halting probability of a universal self-delimiting Turing machine) is wtt-complete, but not tt-complete. In this way we obtain a whole class of natural examples of wtt-complete but not tt-complete r.e. sets. The proof is direct and elementary.

    View record details
  • Most Short Programs Halt Quickly or Never Halt

    Calude, C.S; Stay, M.A (2006-08)

    Report
    The University of Auckland Library

    The aim of this paper is to provide a probabilistic, but non-quantum, 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 N-bit 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 N-bit 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 N-bit program can stop after the time 2N+constant has effectively zero density.

    View record details
  • Embedding Quantum Universes into Classical Ones

    Calude, C.S; Hertling, P.H; Svozil, K (1997-05)

    Report
    The University of Auckland Library

    Do the partial order and lattice operations of a quantum logic correspond to the logical implication and connectives of classical logic? Re-phrased, 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
  • On a Theorem of Solovay

    Calude, C.S; Coles, R.J (1999-02)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Quantum Informatics and the Relations Between Informatics, Physics and Mathematics: A Dialogue

    Calude, C.S; Gruska, J (2007-05)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Dialogues on Quantum Computing

    Calude, C.S (2003-06)

    Report
    The University of Auckland Library

    What 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 constant-position 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 key-ideas on quantum computing.

    View record details
  • Mathematical Proofs at a Crossroad?

    Calude, C.S; Marcus, S (2004-03)

    Report
    The University of Auckland Library

    For more than 2000 years, from Pythagoras and Euclid to Hilbert and Bourbaki, mathematical proofs were essentially based on axiomatic-deductive 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. Axiomatic-deductive proofs are not a posteriori work, a luxury we can marginalize nor are computer-assisted proofs bad mathematics. There is hope for integration!

    View record details
  • Passages of Proof

    Calude, C.S; Calude, E; Marcus, S (2002-02)

    Report
    The University of Auckland Library

    In 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. Computer-assisted 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 (1997-10)

    Report
    The University of Auckland Library

    Following 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 automata-theoretic studies of ω-languages or number theory). To achieve our goal we will use various instruments borrowed from topology, measure-theory, probability theory, number theory, automata and formal languages.

    View record details