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
  • Computing with Cells and Atoms: After Five Years

    Calude, C.S; Paun, G (2004-08)

    Report
    The University of Auckland Library

    This 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
  • 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
  • Quantum Randomness and Value Indefiniteness

    Calude, C.S; Svozil, K (2006-11)

    Report
    The University of Auckland Library

    As 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 (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
  • 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
  • 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
  • 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
  • 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
  • Generalisations of Disjunctive Sequences

    Calude, C.S; Staiger, L (2003-06)

    Report
    The University of Auckland Library

    The 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 (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
  • Natural Halting Probabilities, Partial Randomness, and Zeta Functions

    Calude, C.S; Stay, M.A (2005-11)

    Report
    The University of Auckland Library

    We 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 program-size 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
  • 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
  • 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
  • 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
  • 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 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
  • 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
  • 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