91 results for Calude, C.S, Report

  • On Universal Computably Enumerable Prefix Codes

    Calude, C.S; Staiger, L (2007-10)

    Report
    The University of Auckland Library

    We study computably enumerable (c.e.) prefix codes which are capable of coding all positive integers in an optimal way up to a fixed constant: these codes will be called universal. We prove various characterisations of these codes including the following one: a c.e. prefix code is universal iff it contains the domain of a universal self-delimiting Turing machine. Finally, we study various properties of these codes from the points of view of computability, maximality, and density.

    View record details
  • Supplemental Papers for DLT04

    Calude, C.S; Calude, E; Dinneen, M.J (2004-11)

    Report
    The University of Auckland Library

    These are the papers for the poster talks to be given at the Eighth International Conference on Developments in Language Theory (DLT'04) to be held at Auckland, New Zealand on December 13-17, 2004. The conference is jointly organized by Massey University at Albany and the CDMTCS (New Zealand). The conference, organised under the auspices of the European Association for Theoretical Computer Science (EATCS), is supported by the New Zealand Royal Society.

    View record details
  • Computing a Glimpse of Randomness

    Calude, C.S; Dinneen, Michael; Shu, C.-K (2001-12)

    Report
    The University of Auckland Library

    A Chaitin Omega number is the halting probability of a universal Chaitin (selfdelimiting Turing) machine. Every Omega number is both computably enumerable (the limit of a computable, increasing, converging sequence of rationals) and random (its binary expansion is an algorithmic random sequence). In particular, every Omega number is strongly non-computable. The aim of this paper is to describe a procedure, which combines Java programming and mathematical proofs, for computing the exact values of the first 63 bits of a Chaitin Omega: 000000100000010000100000100001110111001100100111100010010011100. Full description of programs and proofs will be given elsewhere.

    View record details
  • Formal Proof: Reconciling Correctness and Understanding

    Calude, C.S; Müller, C (2009-03)

    Report
    The University of Auckland Library

    Hilbert's concept of formal proof is an ideal of rigour for mathematics which has important applications in mathematical logic, but seems irrelevant for the practice of mathematics. The advent, in the last twenty years, of proof assistants was followed by an impressive record of deep mathematical theorems formally proved. Formal proof is practically achievable. With formal proof, correctness reaches a standard that no pen-and-paper proof can match, but an essential component of mathematics - the insight and understanding - seems to be in short supply. So, what makes a proof understandable? To answer this question we first suggest a list of symptoms of understanding. We then propose a vision of an environment in which users can write and check formal proofs as well as query them with reference to the symptoms of understanding. In this way, the environment reconciles the main features of proof: correctness and understanding.

    View record details
  • Finite Nondeterministic Automata: Simulation and Minimality

    Calude, C.S; Calude, E; Khoussainov, B (1997 -09)

    Report
    The University of Auckland Library

    Motivated by recent applications of finite automata to theoretical physics, we study the minimization problem for nondeterministic automata (with outputs, but no initial states). We use Ehrenfeucht-Fraïsse-like games to model automata responses and simulations. The minimal automaton is constructed and, in contrast with the classical case, proved to be unique up to an isomorphism. Finally, we investigate the partial ordering induced by automata simulations. For example, we prove that, with respect to this ordering, the class of deterministic automata forms an ideal in the class of all automata.

    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
  • 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
  • The Bridge Crossing Problem: Draft Form

    Calude, C.S; Calude, E (2001-09)

    Report
    The University of Auckland Library

    In this note we solve the general case of the Bridge Crossing Problem.

    View record details
  • Supplemental Papers for DMTCS03

    Calude, C.S; Dinneen, Michael; Vajnovszki, V (2003-05)

    Report
    The University of Auckland Library

    These are the papers for the poster talks to be given at the Fourth International Conference Discrete Mathematics and Theoretical Computer Science, 2003, (DMTCS’03) to be held at the Dijon, France on July 7-12, 2003. The conference is jointly organised by the University of Bourgogne (France) and the CDMTCS (New Zealand).

    View record details
  • A Dialogue on Mathematics and Physics

    Calude, C.S; Chaitin, G.J (2006-07)

    Report
    The University of Auckland Library

    As a visiting professor in the Department of Computer Science of the University of Auckland, Greg Chaitin is a frequent visitor in New Zealand. During his recent visit in July 2006 we had time for a dialogue about mathematics, physics, and philosophy— C.S.C.

    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
  • 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
  • Pre-Proceedings of the Workshop on Multiset Processing

    Calude, C.S; Dinneen, Michael; Paun, G (2000-08)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • News from New Zealand / Group-Theoretic Methods for Designing Networks

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

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • On Partial Randomness

    Calude, C.S; Staiger, L; Terwijn, S.A (2004-04)

    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
  • Do the Zeros of the Riemann's Zeta-Function Form a Random Sequence?

    Calude, C.S; Hertling, P.H; Khoussainov, B (1997-04)

    Report
    The University of Auckland Library

    The aim of this note is to introduce the notion of random sequences of reals and to prove that the answer to the question in the title is negative, as anticipated by the informal discussion of Longpré and Kreinovich [15].

    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
  • Evaluating the Complexity of Mathematical Problems. Part 1

    Calude, C.S; Calude, E (2008-12)

    Report
    The University of Auckland Library

    In this paper we provide a computational method for evaluating in a uniform way the complexity of a large class of mathematical problems. The method is illustrated on a variety of examples coming from different areas of mathematics and its power and limits are studied.

    View record details
  • Abstracts of Constructivity, Complexity, and Fuzziness (CCF '99)

    Bridges, D.S; Calude, C.S; Dediu, L.S (1999-07)

    Report
    The University of Auckland Library

    These are the abstracts of talks to be given at the Workshop CCF '99 (Constructivity, Complexity, and Fuzziness) to be held at the University \Dun area de Jos", Galat i, Romania, on 26{28 August 1999. The workshop was organised by the University \Dun area de Jos", Galat i, Romania, the Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, New Zealand and the Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand.

    View record details