27,544 results for ResearchSpace@Auckland

  • Degree-Theoretic Aspects of Computably Enumerable Reals

    Calude, C.S; Coles, R.J; Hertling, P.H; Khoussainov, B (1998-09)

    Report
    The University of Auckland Library

    A real α is computable if its left cut, L(α); is computable. If (qi)i is a computable sequence of rationals computably converging to α, then {qi}, the corresponding set, is always computable. A computably enumerable (c.e.) real is a real which is the limit of an increasing computable sequence of rationals, and has a left cut which is c.e. We study the Turing degrees of representations of c.e. reals, that is the degrees of increasing computable sequences converging to α. For example, every representation A of α is Turing reducible to L(α). Every noncomputable c.e. real has both a computable and noncomputable representation. In fact, the representations of noncomputable c.e. re- als are dense in the c.e. Turing degrees, and yet not every c.e. Turing degree below degT L(α) necessarily contains a representation of α.

    View record details
  • Inexpensive Linear-Optical Implementations of Deutsch's Algorithm

    Stay, M (2004-07)

    Report
    The University of Auckland Library

    Deutsch’s algorithm was the first algorithm proposed for which quantum computers could outperform classical computers. It requires only a single qubit; since photons make very stable qubits, and expensive materials are only needed for multi-qubit gates, one can implement Deutsch’s algorithm using inexpensive, readily available parts. Here we describe two implementations. Such a computer can be useful in demonstrating simple quantum effects.

    View record details
  • Games on Graphs: Automata, Structure, and Complexity

    Khoussainov, B; Kowalski, T (2003-01)

    Report
    The University of Auckland Library

    McNaughton in his known paper [7], motivated by the work of Gurevich and Harrington [4], introduced a class of games played on finite graphs. In his paper McNaughton proves that winners in his games have winning strategies that can be implemented by finite state automata. McNaughton games have attracted attention of many experts in the area, partly because the games have close relationship with automata theory, the study of reactive systems, and logic (see, for instance, [12] and [11]). McNaughton games can also be used to develop game-theoretical approach for many important concepts in computer science such as models for concurrency, communication networks, and update networks, and provide natural examples of computational problems. For example, Nerode, Remmel and Yakhnis in a series of papers (e.g., [8], [9]) developed foundations of concurrent programming in which finite state strategies of McNaughton games are identified with distributed concurrent programs. -- from Introduction

    View record details
  • A Genius' Story: Two Books on Godel

    Calude, C.S (1997-06)

    Report
    The University of Auckland Library

    Undoubtly, Gödel was the greatest logician of the twentieth century. There is no trace of exaggeration in saying, following Wang, that Gödel's contribution to mathematics has the same status as Freudian psychology, Einstein's theory of relativity, Bohr's principle of complementarity, Heisenberg's uncertainty principle, keynesian economics, and Watson and Crick double helix model of DNA. Yet, with a few notable exceptions, most of the personal details of Gödel's life remained a mystery

    View record details
  • Chaitin $\Omega$ Numbers, Solovay Machines, and Incompleteness

    Calude, C.S (1999-10)

    Report
    The University of Auckland Library

    Computably enumerable (c.e.) reals can be coded by Chaitin machines through their halting probabilities. Tuning Solovay's construction of a Chaitin universal machine for which ZFC (if arithmetically sound) cannot determine any single bit of the binary expansion of its halting probability, we show that every c.e. random real is the halting probability of a universal Chaitin machine for which ZFC cannot determine more than its initial block of 1 bits – as soon as you get a 0 it's all over. Finally, a constructive version of Chaitin information-theoretic incompleteness theorem is proven.

    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
  • 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
  • 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
  • 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
  • Relations Between the Low Subrecursion Classes

    Grozea, C (2001-07)

    Report
    The University of Auckland Library

    [no abstract available]

    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
  • On Hypersimple Sets and Chaitin Complexity

    Arslanov, A (1998-04)

    Report
    The University of Auckland Library

    In this paper we study some computability theoretic properties of two notions of randomness for finite strings: randomness based on the blank-endmarker complexity measure and Chaitin randomness based on the self-delimiting complexity measure. For example, we find the position of RANDK and RANDC at the same level in the scale of immunity notions by proving that both of them are not hyperimmune sets. Also we introduce a new notion of complex infinite sequences of finite strings. We call them K-bounded sequences.

    View record details
  • Asymptotics of Diagonal Coefficients of Multivariate Generating Functions

    Raichev, A; Wilson, Mark (2007-05)

    Report
    The University of Auckland Library

    This article presents some recent progress in the asymptotics of diagonal coefficients of multivariate generating functions and can be seen as an extension of [RW].

    View record details
  • Probability Calculations Under the IAC Hypothesis

    Pritchard, G; Wilson, Mark (2006-10)

    Report
    The University of Auckland Library

    We show how powerful algorithms recently developed for counting lattice points and computing volumes of convex polyhedra can be used to compute probabilities of a wide variety of events of interest in social choice theory. Several illustrative examples are given.

    View record details
  • 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
  • Complexity and Randomness

    Terwijn, S.A (2003-03)

    Report
    The University of Auckland Library

    [no abstract available]

    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
  • Design and Evaluation of Slicing Obfuscation

    Drape, S; Majumdar, A (2007-06)

    Report
    The University of Auckland Library

    The goal of obfuscation is to transform a program, without affecting its functionality, so that some secret information within the program can be hidden for as long as possible from an adversary armed with reverse engineering tools. Slicing is a form of reverse engineering which aims to abstract away a subset of program code based on a particular program point and is considered to be a potent program comprehension technique. Thus, slicing could be used as a way of attacking obfuscated programs. It is challenging to manufacture obfuscating transforms that are provably resilient to slicing attacks. We show in this paper how we can utilise the information gained from slicing a program to aid us in designing obfuscations that are more resistant to slicing. We extend a previously proposed technique and provide proofs of correctness for our transforms. Finally, we illustrate our approach with a number of obfuscating transforms and provide empirical results.

    View record details
  • The min-max Principle Generalizes Tsirelson's Bound

    Filipp, S; Svozil, K (2004-04)

    Report
    The University of Auckland Library

    Bounds on the norm of quantum operators associated with classical Bell-type inequalities can be derived from their maximal eigenvalues. This quantitative method enables detailed predictions of the maximal violations of Bell-type inequalities.

    View record details
  • Finding a State in a Haystack

    Donath, N; Svozil, K (2001-05)

    Report
    The University of Auckland Library

    We consider the problem to single out a particular state among 2n orthogonal pure states. As it turns out, in general the optimal strategy is not to measure the particles separately, but to consider joint properties of the n-particle system. The required number of propositions is n. There exist 2n! equivalent operational procedures to do so. We enumerate some configurations for three particles, in particular the Greenberger-Horne-Zeilinger (GHZ) and W-states, which are specific cases of a unitary transformation. For the GHZ-case, an explicit physical meaning of the projection operators is discussed.

    View record details