91 results for Calude, C.S, Report

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 
Computing with Cells and Atoms: After Five Years
Calude, C.S; Paun, G (200408)
Report
The University of Auckland LibraryThis 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 (200306)
Report
The University of Auckland LibraryWhat 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 constantposition 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 keyideas on quantum computing.
View record details 
Quantum Randomness and Value Indefiniteness
Calude, C.S; Svozil, K (200611)
Report
The University of Auckland LibraryAs 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 (200608)
Report
The University of Auckland LibraryThe aim of this paper is to provide a probabilistic, but nonquantum, 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 Nbit 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 Nbit 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 Nbit 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 (199705)
Report
The University of Auckland LibraryDo the partial order and lattice operations of a quantum logic correspond to the logical implication and connectives of classical logic? Rephrased, 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 (199912)
Report
The University of Auckland LibraryWe 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 (NPcomplete) 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 (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 
A New Measure of the Difficulty of Problems
Calude, C.S; Calude, E; Dinneen, Michael (200602)
Report
The University of Auckland LibraryGuessing 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 (199710)
Report
The University of Auckland LibraryFollowing 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 automatatheoretic studies of ωlanguages or number theory). To achieve our goal we will use various instruments borrowed from topology, measuretheory, probability theory, number theory, automata and formal languages.
View record details 
Generalisations of Disjunctive Sequences
Calude, C.S; Staiger, L (200306)
Report
The University of Auckland LibraryThe 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 (199708)
Report
The University of Auckland LibraryFinite 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 (200511)
Report
The University of Auckland LibraryWe 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 programsize 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 (200403)
Report
The University of Auckland LibraryFor more than 2000 years, from Pythagoras and Euclid to Hilbert and Bourbaki, mathematical proofs were essentially based on axiomaticdeductive 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. Axiomaticdeductive proofs are not a posteriori work, a luxury we can marginalize nor are computerassisted proofs bad mathematics. There is hope for integration!
View record details 
Supplemental Papers for DLT04
Calude, C.S; Calude, E; Dinneen, M.J (200411)
Report
The University of Auckland LibraryThese 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 1317, 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 (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 
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 Bridge Crossing Problem: Draft Form
Calude, C.S; Calude, E (200109)
Report
The University of Auckland LibraryIn 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 (200607)
Report
The University of Auckland LibraryAs 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 (199902)
Report
The University of Auckland Library[no abstract available]
View record details