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 
Incompleteness, Complexity, Randomness and Beyond
Calude, C.S (200111)
Report
The University of Auckland LibraryGö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 informationtheoretic approach to randomness and recent developments in quantum computing.
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 
Randomness Relative to Cantor Expansions
Calude, C.S; Staiger, L; Svozil, K (200304)
Report
The University of Auckland LibraryImagine 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 (200706)
Report
The University of Auckland LibraryThere 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 (199902)
Report
The University of Auckland LibraryThis 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 (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 
Real Numbers: From Computable to Random
Calude, C.S (200008)
Report
The University of Auckland LibraryA 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 (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 
Preproceedings 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 (200111)
Report
The University of Auckland LibraryThe Workshop is part of the Australasian Association of Philosophy (New Zealand Division) Annual Conference to be held in Auckland, New Zealand on 27 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 (199710)
Report
The University of Auckland LibraryWe prove that any Chaitin Ω number (i.e., the halting probability of a universal selfdelimiting Turing machine) is wttcomplete, but not ttcomplete. In this way we obtain a whole class of natural examples of wttcomplete but not ttcomplete 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 (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 
On a Theorem of Solovay
Calude, C.S; Coles, R.J (199902)
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 (200705)
Report
The University of Auckland Library[no abstract available]
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 
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 
Passages of Proof
Calude, C.S; Calude, E; Marcus, S (200202)
Report
The University of Auckland LibraryIn 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. Computerassisted 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 (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