27,544 results for ResearchSpace@Auckland

DegreeTheoretic Aspects of Computably Enumerable Reals
Calude, C.S; Coles, R.J; Hertling, P.H; Khoussainov, B (199809)
Report
The University of Auckland LibraryA 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 LinearOptical Implementations of Deutsch's Algorithm
Stay, M (200407)
Report
The University of Auckland LibraryDeutsch’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 multiqubit 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 (200301)
Report
The University of Auckland LibraryMcNaughton 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 gametheoretical 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 (199706)
Report
The University of Auckland LibraryUndoubtly, 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 (199910)
Report
The University of Auckland LibraryComputably 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 informationtheoretic incompleteness theorem is proven.
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 
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 
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 
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 
Relations Between the Low Subrecursion Classes
Grozea, C (200107)
Report
The University of Auckland Library[no abstract available]
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 
On Hypersimple Sets and Chaitin Complexity
Arslanov, A (199804)
Report
The University of Auckland LibraryIn this paper we study some computability theoretic properties of two notions of randomness for finite strings: randomness based on the blankendmarker complexity measure and Chaitin randomness based on the selfdelimiting 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 Kbounded sequences.
View record details 
Asymptotics of Diagonal Coefficients of Multivariate Generating Functions
Raichev, A; Wilson, Mark (200705)
Report
The University of Auckland LibraryThis 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 (200610)
Report
The University of Auckland LibraryWe 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 (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 
Complexity and Randomness
Terwijn, S.A (200303)
Report
The University of Auckland Library[no abstract available]
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 
Design and Evaluation of Slicing Obfuscation
Drape, S; Majumdar, A (200706)
Report
The University of Auckland LibraryThe 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 minmax Principle Generalizes Tsirelson's Bound
Filipp, S; Svozil, K (200404)
Report
The University of Auckland LibraryBounds on the norm of quantum operators associated with classical Belltype inequalities can be derived from their maximal eigenvalues. This quantitative method enables detailed predictions of the maximal violations of Belltype inequalities.
View record details 
Finding a State in a Haystack
Donath, N; Svozil, K (200105)
Report
The University of Auckland LibraryWe 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 nparticle 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 GreenbergerHorneZeilinger (GHZ) and Wstates, which are specific cases of a unitary transformation. For the GHZcase, an explicit physical meaning of the projection operators is discussed.
View record details