2020-10-26T21:59:49Zhttps://researchspace.auckland.ac.nz/dspace-oai/requestoai:researchspace.auckland.ac.nz:2292/35092012-02-02T23:23:13Zcom_2292_122col_2292_3508An initial-algebra approach to directed acyclic graphsGibbons, JennyThe initial-algebra approach to modelling datatypes consists of giving constructors
for building larger objects of that type from smaller ones, and laws identifying different ways
of constructing the same object. The recursive decomposition of objects of the datatype leads
directly to a recursive pattern of computation on those objects, which is very helpful for both
functional and parallel programming.
We show how to model a particular kind of directed acyclic graph using this initial-algebra
approach.2009-04-142009-04-141995-04Technical ReportCDMTCS Research Report Series CDMTCS-001 (1995)http://hdl.handle.net/2292/3509CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36652012-02-02T23:23:17Zcom_2292_122col_2292_3508A Conference Submission Web ServerLee, S.Y.PDinneen, MichaelWe present a conference submission web server that supports conference
organizers to manage the process of receiving and evaluating conference papers.
The main features of our conference submission web server include effective
operations and transactions, simple and flexible user interfaces, platform
independence and reusability. The system models a conference organized by the
Center for Discrete Mathematics and Theoretical Computer Science
(Auckland, New Zealand). It is designed and implemented as a standalone
application. It can be, however easily plugged into an existing conference web
site.2009-04-162009-04-162001-06Technical ReportCDMTCS Research Reports CDMTCS-157 (2001)1178-3540http://hdl.handle.net/2292/3665CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37472012-02-02T23:23:13Zcom_2292_122col_2292_3508Automata Recognizing No Words: A Statistical ApproachCalude, C.SCampeanu, CDumitrescu, MHow likely is that a randomly given (non-) deterministic finite automaton recognizes no
word? A quick reflection seems to indicate that not too many finite automata accept no word;
but, can this intuition be confirmed?
In this paper we offer a statistical approach which allows us to conclude that for automata,
with a large enough number of states, the probability that a given (non-) deterministic finite
automaton recognizes no word is close to zero. More precisely, we will show, with a high
degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for
both deterministic and non-deterministic finite automata: a) the probability that an automaton
recognizes no word tends to zero when the number of states and the number of letters in the
alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the
number of letters of the alphabet of the automaton tends to infinity, the probability is strictly
positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and
statistical analysis.
The present analysis shows that for all practical purposes the fraction of automata recognizing
no words tends to zero when the number of states and the number of letters in the alphabet
grow indefinitely.
In the last section we critically discuss the method and result obtained in this paper. From
a theoretical point of view, the result can motivate the search for “certitude”, that is, a proof
of the fact established here in probabilistic terms. In fact, the method used is much more
important than the result itself. The method is “general” in the sense that it can be applied to
a variety of questions in automata theory, certainly some more difficult than the problem solved
in this note.2009-04-162009-04-162004-05Technical ReportCDMTCS Research Reports CDMTCS-240 (2004)1178-3540http://hdl.handle.net/2292/3747CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37272012-02-02T23:23:17Zcom_2292_122col_2292_3508A Fast Natural Algorithm for SearchingArulanandham, J.JCalude, C.SDinneen, MichaelIn this note we present two natural algorithms—one for sorting, and another
for searching a sorted list of items. Both algorithms work in O(√N) time, N being
the size of the list. A combination of these algorithms can search an unsorted list
in O(√N) time, an impossibility for classical algorithms. The same complexity is
achieved by Grover’s quantum search algorithm; in contrast to Grover’s algorithm
which is probabilistic, our method is guaranteed correct. Two applications will
conclude this note.2009-04-162009-04-162003-06Technical ReportCDMTCS Research Reports CDMTCS-220 (2003)1178-3540http://hdl.handle.net/2292/3727CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35732012-02-02T23:23:16Zcom_2292_122col_2292_3508Surjective Functions on Computably Growing Cantor SetsHertling, PEvery infinite binary sequence is Turing reducible to a random one. This is
a corollary of a result of Peter Gacs stating that for every co-r.e. closed set with
positive measure of infinite sequences there exists a computable mapping which
maps a subset of the set onto the whole space of infinite sequences. Cristian
Calude asked whether in this result one can replace the positive measure condition by a weaker condition not involving the measure. We show that this is
indeed possible: it is sufficient to demand that the co-r.e. closed set contains a
computably growing Cantor set. Furthermore, in the case of a set with positive
measure we construct a surjective computable map which is more effective than
the map constructed by Gacs.2009-04-162009-04-161997-10Technical ReportCDMTCS Research Reports CDMTCS-064 (1997)1178-3540http://hdl.handle.net/2292/3573CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37682012-02-02T23:23:13Zcom_2292_122col_2292_3508What is the Value of Taxicab(6)? An UpdateCalude, C.SCalude, EDinneen, MichaelThe famous story of the number 1729, the smallest integer which can be expressed
as the sum of two positive cubes in two different ways, motivated the
introduction of Taxicab Numbers. The smallest number expressible as the sum of
two cubes in n different ways is called Taxicab(n). So, Taxicab(2) = 1729. Further
on, Taxicab(5) = 48988659276962496. Computing Taxicab(n) is challenging and
interesting, both from mathematical and programming points of view.
The exact value of Taxicab(6) is not known; in view of the results obtained
by Bernstein [1] and Rathbun [14] it follows that Taxicab(6) is in the interval
[10¹⁸, 24153319581254312065344]. In [5] we proved that with probability greater
than 99%, Taxicab(6) = 24153319581254312065344.
In this note we improve the method used in [5] in two ways: we use (1) a larger,
and (2) a better quality random sampling, namely, a sample of 562,500 quantum
random integers drawn from the above mentioned interval using Quantis, [10]. As a
result, we prove that the above value for Taxicab(6) is true with probability greater
than 99.8%.2009-04-162009-04-162005-04Technical ReportCDMTCS Research Reports CDMTCS-261 (2005)1178-3540http://hdl.handle.net/2292/3768CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36272012-02-02T23:23:17Zcom_2292_122col_2292_3508The Minor-Order Obstructions for The Graphs of Vertex Cover SixDinneen, MichaelXiong, LiuWe provide for the first time a complete list of forbidden minors (obstructions)
for the family of graphs with vertex cover 6. This paper shows how to
limit both the search space of graphs and improve the efficiency of an obstruction
checking algorithm when restricted to k–Vertex Cover graph families.
In particular, our upper bounds 2k + 1 (2k + 2) on the maximum number of
vertices for connected (disconnected) obstructions are shown to be sharp for all
k > 0.2009-04-162009-04-162000-01Technical ReportCDMTCS Research Reports CDMTCS-118 (2000)1178-3540http://hdl.handle.net/2292/3627CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36952012-02-02T23:23:13Zcom_2292_122col_2292_3508Another Example of Higher Order RandomnessBecher, VChaitin, G.JWe consider the notion of randomness relative to an oracle: a real number is
random in A if and only if its initial segments are algorithmically incompressible
in a self-delimiting universal machine equipped with an oracle A. We prove that
the probability that a program for infinite computations outputs a cofinite set is
random in the second jump of the halting problem.2009-04-162009-04-162002-05Technical ReportCDMTCS Research Reports CDMTCS-187 (2002)1178-3540http://hdl.handle.net/2292/3695CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36242012-02-02T23:23:13Zcom_2292_122col_2292_3508Computable $p$-adic NumbersKapoulas, GIn the present work the notion of the computable (primitive recursive,
polynomially time computable) p-adic number is introduced and studied. Basic properties
of these numbers and the set of indices representing them are established and it
is proved that the above defined fields are p-adically closed. Using the notion of a notation
system introduced by Y. Moschovakis an abstract characterization of the indices
representing the field of computable p-adic numbers is established.2009-04-162009-04-161999-11Technical ReportCDMTCS Research Reports CDMTCS-115 (1999)1178-3540http://hdl.handle.net/2292/3624CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37712012-02-02T23:23:15Zcom_2292_122col_2292_3508Infinite Iterated Function Systems in Cantor Space and the Hausdorff Measure of omega-power LanguagesStaiger, LWe use means of formal language theory to estimate the Hausdorff measure
of sets of a certain shape in Cantor space. These sets are closely related
to infinite iterated function systems in fractal geometry.
Our results are used to provide a series of simple examples for the noncoincidence
of limit sets and attractors for infinite iterated function systems.2009-04-162009-04-162005-04Technical ReportCDMTCS Research Reports CDMTCS-264 (2005)1178-3540http://hdl.handle.net/2292/3771CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37742012-02-02T23:23:13Zcom_2292_122col_2292_3508A Comparison of Practical Information MeasuresTitchener, M.RSpeidel, UYang, JThis report compares a variety of computable information measures for finite strings. These include
Shannon’s n-block entropy, the three best known versions of the Lempel-Ziv production complexity
(LZ-76, LZ-77, and LZ-78), and the lesser known T-entropy. We apply these measures to strings of
known entropy, each derived from the logistic map. Pesin’s identity allows us to deduce corresponding
Shannon entropies (Kolmogorov-Sinai entropies) for the sample strings, without resorting to probabilistic
methods.2009-04-162009-04-162005-05Technical ReportCDMTCS Research Reports CDMTCS-267 (2005)1178-3540http://hdl.handle.net/2292/3774CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37962012-02-02T23:23:18Zcom_2292_122col_2292_3508Longest Alternating Subsequences in Pattern-Restricted PermutationsFirror, GMansour, TWilson, MarkInspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations, and the results of Deutsch, Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations, we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences, generating functions, and complex analysis, and also yields more detailed information. Several ideas for future research are listed.2009-04-162009-04-162006-10Technical ReportCDMTCS Research Reports CDMTCS-289 (2006)1178-3540http://hdl.handle.net/2292/3796CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37932012-02-02T23:23:16Zcom_2292_122col_2292_3508T-Complexity and T-Information Theory--an Executive Summary, 2nd revised versionSpeidel, UThis paper describes the derivation of the T-complexity and T-in-
formation theory from the decomposition of finite strings, based on the
duality of strings and variable-length T-codes. It further outlines its similarity to the string parsing algorithm by Lempel and Ziv. In its first
version [15], it was intended as a summary of work published mainly by
Titchener and Nicolescu. Apart from minor corrections, the present extended version incorporates feedback from previous readers and presents
new results obtained since.2009-04-162009-04-162006-10Technical ReportCDMTCS Research Reports CDMTCS-286 (2006)1178-3540http://hdl.handle.net/2292/3793CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35742012-02-02T23:23:14Zcom_2292_122col_2292_3508Embedding Cellular Automata into Reversible OnesHertling, PToffoli showed that every cellular automaton of an arbitrary dimension d can be embedded into a
reversible cellular automaton of dimension d+1. He asked “whether an arbitrary cellular automaton
can be embedded in a reversible one having the same number of dimensions” and conjectured that
this is not possible. We show that his conjecture is true. Even if one imposes only a weak, natural
condition on embeddings, no cellular automaton which possesses a Garden of Eden configuration
can be embedded into a reversible cellular automaton of the same dimension.2009-04-162009-04-161997-10Technical ReportCDMTCS Research Reports CDMTCS-065 (1997)1178-3540http://hdl.handle.net/2292/3574CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38672012-02-02T23:23:14Zcom_2292_122col_2292_3508On the Brightness of the Thomson lamp. A Prolegomenon to Quantum Recursion TheorySvozil, KSome quantum cryptographic protocols can be implemented with specially prepared
chocolate balls, others protected by value indefiniteness cannot. Similarities and differences
of cryptography with quanta and chocolate are discussed. Motivated by these considerations
it is proposed to certify quantum random number generators and quantum cryptographic
protocols by value indefiniteness. This feature, which derives itself from Belland
Kochen-Specker type arguments, is only present in systems with three or more mutually
exclusive outcomes.2009-04-162009-04-162009-04Technical ReportCDMTCS Research Reports CDMTCS-360 (2009)1178-3540http://hdl.handle.net/2292/3867CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37922012-02-02T23:23:15Zcom_2292_122col_2292_3508De-Quantising the Solution of Deutsch's ProlemCalude, C.SProbably the simplest and most frequently used way to illustrate the power of quantum
computing is to solve the so-called Deutsch’s problem. Consider a Boolean function f :
{0,1}→{0,1} and suppose that we have a (classical) black box to compute it. The problem
asks whether f is constant (that is, f (0) = f (1)) or balanced ( f (0) ≠ f (1)). Classically, to
solve the problem seems to require the computation of f (0) and f (1), and then the comparison
of results. Is it possible to solve the problem with only one query on f ? In a famous paper
published in 1985, Deutsch posed the problem and obtained a “quantum” partial affirmative
answer. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello,
and Mosca. Here we will show that the quantum solution can be de-quantised to a
deterministic simpler solution which is as efficient as the quantum one. The use of “superposition”,
a key ingredient of quantum algorithm, is—in this specific case—classically available.2009-04-162009-04-162006-08Technical ReportCDMTCS Research Reports CDMTCS-285 (2006)1178-3540http://hdl.handle.net/2292/3792CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36932012-02-02T23:23:17Zcom_2292_122col_2292_3508Some Thoughts On Automatic StructuresKhoussainov, BRubin, SOur aim in writing this paper is twofold. On the one hand, we present the theory
of automatic structures from the points of view of model theory, algebra, complexity
theory, and automata theory. On the other hand, we survey basic results and present
possible directions for future research in the area.
--from Introduction2009-04-162009-04-162002-05Technical ReportCDMTCS Research Reports CDMTCS-185 (2002)1178-3540http://hdl.handle.net/2292/3693CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37702012-02-02T23:23:13Zcom_2292_122col_2292_3508Twenty Combinatorial Examples of Asymptotics Derived From Multivariate Generating FunctionsPemantle, RWilson, MarkThe purpose of this paper is to review recent developments in the asymptotics of
multivariate generating functions, and to give an exposition of these that is accessible
and centered around applications. We begin, however, with a brief review of univariate
generating functions and of previous results on multivariate generating functions.2009-04-162009-04-162005-04Technical ReportCDMTCS Research Reports CDMTCS-263 (2005)1178-3540http://hdl.handle.net/2292/3770CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36672012-02-02T23:23:13Zcom_2292_122col_2292_3508A Constructive Theory of Point-Set NearnessBridges, D.SVita, L.SAn axiomatic constructive development of the theory of nearness and apartness
of a point and a set is introduced as a setting for topology.2009-04-162009-04-162001-08Technical ReportCDMTCS Research Reports CDMTCS-159 (2001)1178-3540http://hdl.handle.net/2292/3667CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37492012-02-02T23:23:17Zcom_2292_122col_2292_3508Fast Generation of Fibonacci PermutationsJuarna, AVajnovszki, V[no abstract available]2009-04-162009-04-162004-07Technical ReportCDMTCS Research Reports CDMTCS-242 (2004)1178-3540http://hdl.handle.net/2292/3749CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35932012-02-02T23:23:18Zcom_2292_122col_2292_3508Breaking the Turing BarrierCalude, C.SDinneen, MichaelIs there any limit to discrete computation, and more generally, to scientific knowledge? This is one of the problems studied by the Centre for Discrete Mathematics and
Theoretical Computer Science of the University of Auckland.2009-04-162009-04-161998-05Technical ReportCDMTCS Research Reports CDMTCS-084 (1998)1178-3540http://hdl.handle.net/2292/3593CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36002012-02-02T23:23:17Zcom_2292_122col_2292_3508Abstracts of the 2nd Japan - New Zealand Workshop on Logic in Computer ScienceDinneen, M.J[no abstract available]2009-04-162009-04-161998-10Technical ReportCDMTCS Research Reports CDMTCS-091 (1998)1178-3540http://hdl.handle.net/2292/3600CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37912012-02-02T23:23:17Zcom_2292_122col_2292_3508Most Short Programs Halt Quickly or Never HaltCalude, C.SStay, M.AThe 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.2009-04-162009-04-162006-08Technical ReportCDMTCS Research Reports CDMTCS-284 (2006)1178-3540http://hdl.handle.net/2292/3791CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37722012-02-02T23:23:17Zcom_2292_122col_2292_3508Very Simple Chaitin Machines for Concrete AITStay, MIn 1975, Chaitin introduced his celebrated Omega number, the
halting probability of a universal Chaitin machine, a universal Turing machine
with a prefix-free domain. The Omega number’s bits are algorithmically
random—there is no reason the bits should be the way they are, if we define
“reason” to be a computable explanation smaller than the data itself. Since
that time, only two explicit universal Chaitin machines have been proposed,
both by Chaitin himself.
Concrete algorithmic information theory involves the study of particular
universal Turing machines, about which one can state theorems with specific
numerical bounds, rather than include terms like O(1). We present several
new tiny Chaitin machines (those with a prefix-free domain) suitable for the
study of concrete algorithmic information theory. One of the machines, which
we call Keraia, is a binary encoding of lambda calculus based on a curried
lambda operator. Source code is included in the appendices.
We also give an algorithm for restricting the domain of blank-endmarker
machines to a prefix-free domain over an alphabet that does not include the
endmarker; this allows one to take many universal Turing machines and construct
universal Chaitin machines from them.2009-04-162009-04-162005-05Technical ReportCDMTCS Research Reports CDMTCS-265 (2005)1178-3540http://hdl.handle.net/2292/3772CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36442012-02-02T23:23:16Zcom_2292_122col_2292_3508Presentations of Computably Enumerable RealsDowney, R.GLaForte, G.LWe study the relationship between a computably enumerable real
and its presentations: ways of approximating the real by enumerating
a pre x-free set of binary strings.2009-04-162009-04-162000-05Technical ReportCDMTCS Research Reports CDMTCS-135 (2000)1178-3540http://hdl.handle.net/2292/3644CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35212012-02-02T23:23:14Zcom_2292_122col_2292_3508Quantum Electronic Devices Based on Metal-Dielectric Transition in Low-Dimensional Quantum StructuresAntoniou, IPavlov, BYafyasov, A[no abstract available]2009-04-162009-04-161996-04Technical ReportCDMTCS Research Reports CDMTCS-012 (1996)1178-3540http://hdl.handle.net/2292/3521CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36452012-02-02T23:23:15Zcom_2292_122col_2292_3508Quantum InterfacesSvozil, KRational agents acting as observers use “knowables” to construct a vision of the outside world.
Thereby, they are bound by the information exchanged with what they consider as objects. The
cartesian cut or, in modern terminology, the interface mediating this exchange, is again a construction.
It serves as a “scaffolding,” an intermediate construction capable of providing the necessary
conceptual means.
An attempt is made to formalize the interface, in particular the quantum interface and quantum
measurements, by a symbolic information exchange. A principle of conservation of information is
reviewed and a measure of information flux through the interface is proposed.
We cope with the question of why observers usually experience irreversibility in measurement
processes if the evolution is reversible, i.e., one-to-one. And why should there be any meaningful
concept of classical information if there is merely quantum information to begin with? We take the
position here that the concept of irreversible measurement is no deep principle but originates in the
practical inability to reconstruct a quantum state of the object.
Many issues raised apply also to the quantum’s natural double, virtual reality.
An experiment is proposed to test the conjecture that the self is transcendent.2009-04-162009-04-162000-05Technical ReportCDMTCS Research Reports CDMTCS-136 (2000)1178-3540http://hdl.handle.net/2292/3645CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35222012-02-02T23:23:15Zcom_2292_122col_2292_3508Kraft-Chaitin Inequality RevisitedCalude, CGrozea, CKraft's inequality [9] is essential for the classical theory of noiseless coding [1, 8]. In algorithmic
information theory [5, 7, 2] one needs an extension of Kraft's condition from finite sets to (infinite)
recursively enumerable sets. This extension, known as Kraft-Chaitin Theorem, was obtained by
Chaitin in his seminal paper [4] (see also, [3, 2], [10]). The aim of this note is to offer a simpler proof
of Kraft-Chaitin Theorem based on a new construction of the prefix-free code.2009-04-162009-04-161996-04Technical ReportCDMTCS Research Reports CDMTCS-013 (1996)1178-3540http://hdl.handle.net/2292/3522CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37952012-02-02T23:23:19Zcom_2292_122col_2292_3508The Diameter of Random Cayley Digraphs of Given DegreeLladser, M.EPotocnik, PSiran, JSiagiova, JWilson, M.CWe consider random Cayley digraphs of order n with uniformly distributed
generating set of size k. Specifically, we are interested in the asymptotics of the
probability such a Cayley digraph has diameter two as n →∞ and k = f(n). We
find a sharp phase transition from 0 to 1 as the order of growth of f(n) increases
past √log n. In particular, if f(n) is asymptotically linear in n, the probability
converges exponentially fast to 1.2009-04-162009-04-162006-10Technical ReportCDMTCS Research Reports CDMTCS-288 (2006)1178-3540http://hdl.handle.net/2292/3795CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35912012-02-02T23:23:14Zcom_2292_122col_2292_3508News from New Zealand / Group-Theoretic Methods for Designing NetworksCalude, C.SDinneen, Michael[no abstract available]2009-04-162009-04-161998-05Technical ReportCDMTCS Research Reports CDMTCS-082 (1998)1178-3540http://hdl.handle.net/2292/3591CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37892012-02-02T23:23:14Zcom_2292_122col_2292_3508Speculations on Biology, Information and ComplexityChaitin, G.JIt would be nice to have a mathematical understanding of basic biological concepts
and to be able to prove that life must evolve in very general circumstances.
At present we are far from being able to do this. But I’ll discuss some partial steps
in this direction plus what I regard as a possible future line of attack.2009-04-162009-04-162006-07Technical ReportCDMTCS Research Reports CDMTCS-282 (2006)1178-3540http://hdl.handle.net/2292/3789CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37732012-02-02T23:23:18Zcom_2292_122col_2292_3508Network Event Detection with T-EntropyEimann, RSpeidel, UBrownlee, NYang, JThis paper describes an entropy-based approach for the detection of network events.
This is achieved by first converting a stream of network packets into a string and then
computing its approximate average entropy rate using a computable complexity measure.
Changes in the average entropy rate are interpreted as events. The computational
complexity of the presented approach is nearly linear which makes this technique suitable
for online scenarios. We present the results of several measurements on actual
network data and show that it is indeed possible to associate actual network events
with changes in entropy.2009-04-162009-04-162005-05Technical ReportCDMTCS Research Reports CDMTCS-266 (2005)1178-3540http://hdl.handle.net/2292/3773CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36422012-02-02T23:23:15Zcom_2292_122col_2292_3508Computational Methods and New Results for Chessboard ProblemsKearse, M.DGibbons, P.BWe describe various computing techniques for tackling chessboard domination problems
and apply these to the determination of domination and irredundance numbers
for queens’ and kings’ graphs. In particular we show that γ(Q15) = γ(Q16) = 9 ,
confirm that γ(Q17) = γ(Q18) = 9, show that γ(Q19) = 10, show that i(Q18) = 10,
improve the bound for i(Q19) to 10 ≤ i(Q19) ≤ 11, show that ir(Qn) = γ(Qn) for
1 ≤ n ≤ 13, show that IR(Q9) = Γ(Q9) = 13 and that IR(Q10) = Γ(Q10) = 15, show
that γ(Q4k+1) = 2k +1 for 16 ≤ k ≤ 21, improve the bound for i(Q22) to i(Q22) ≤ 12,
and show that IR(K8) = 17, IR(K9) = 25, IR(K10) = 27, and IR(K11) = 36.2009-04-162009-04-162000-05Technical ReportCDMTCS Research Reports CDMTCS-133 (2000)1178-3540http://hdl.handle.net/2292/3642CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36072012-02-02T23:23:16Zcom_2292_122col_2292_3508Computing with Membranes: A VariantPaun, GWe propose here a variant of the super-cell systems (also called, for
short, P systems), which looks less restrictive (more realistic) than the variants
investigated so far. In P systems as introduced in [7] (see a survey in [8]), the use
of objects evolution rules is regulated by a given priority relation; moreover, each
membrane has a label and one can send objects to precise membranes, identified
by their labels. We get rid of both there rather artificial (non-biochemical) features. Instead, we add to membranes and to objects an \electrical charge" and
the objects are passed through membranes according to their charge. We prove
that such systems are able to characterize the one-letter recursively enumerable
languages (equivalently, the recursively enumerable sets of natural numbers),
providing that an extra feature is considered: the membranes can be made
thicker or thinner (also dissolved, as in [7]) and the communication through
a membrane is possible only when its thickness is equal to 1. Several open
problems are formulated.2009-04-162009-04-161999-03Technical ReportCDMTCS Research Reports CDMTCS-098 (1999)1178-3540http://hdl.handle.net/2292/3607CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35922012-02-02T23:23:15Zcom_2292_122col_2292_3508Computational Complementarity for Mealy AutomataCalude, C.SCalude, EStefanescu, CIn this paper we extend (and study) two computational complementary principles from Moore to Mealy automata which are finite machines possessing better “quantum-like” features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett’s method, for example). Mathematica experiments confirmed this hypothesis.2009-04-162009-04-161998-05Technical ReportCDMTCS Research Reports CDMTCS-083 (1998)1178-3540http://hdl.handle.net/2292/3592CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35752012-02-02T23:23:17Zcom_2292_122col_2292_3508Feedback for RelationsCazanescu, V.EIn our previous papers [3,2] we have proved that there are nine types of finite relations
which are closed under a natural definition of feedback. In this note we prove that this
natural definition is the unique feedback which satisfies the axioms of a biflow over there
usual composition and sum.2009-04-162009-04-161997-11Technical ReportCDMTCS Research Reports CDMTCS-066 (1997)1178-3540http://hdl.handle.net/2292/3575CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37882012-02-02T23:23:17Zcom_2292_122col_2292_3508Is Incompleteness A Serious ProblemChaitin, G.J[no abstract available]2009-04-162009-04-162006-07Technical ReportCDMTCS Research Reports CDMTCS-281 (2006)1178-3540http://hdl.handle.net/2292/3788CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35192012-02-02T23:23:18Zcom_2292_122col_2292_3508Higman's Embedding Theorem. An Elementary ProofDediu, LIn 1961 G. Higman proved a remarkable theorem establishing a deep connection between the
logical notion of recursiveness and questions about finitely presented groups.
The basic aim of the present paper is to provide the reader with a rigorous and detailed proof
of Higman's Theorem. All the necessary preliminary material, including elements of group theory
and recursive functions theory, is systematically presented and with complete proofs. The aquainted
reader may skip the first sections and proceed immediately to the last.2009-04-162009-04-161995-10Technical ReportCDMTCS Research Reports CDMTCS-010 (1995)1178-3540http://hdl.handle.net/2292/3519CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37442012-02-02T23:23:19Zcom_2292_122col_2292_3508Finite Automata Encoding Geometric FiguresJuergensen, HStaiger, LYamasaki, HFinite automata are used for the encoding and compression of images. For
black-and-white images, for instance, using the quad-tree representation, the
black points correspond to ω-words defining the corresponding paths in the
tree that lead to them. If the ω-language consisting of the set of all these
words is accepted by a deterministic finite automaton then the image is said
to be encodable as a finite automaton. For grey-level images and colour images
similar representations by automata are in use.
In this paper we address the question of which images can be encoded as
finite automata with full infinite precision. In applications, of course, the image
would be given and rendered at some finite resolution – this amounts to
considering a set of finite prefixes of the ω-language – and the features in the
image would be approximations of the features in the infinite precision rendering.
We focus on the case of black-and-white images – geometrical figures, to
be precise – but treat this case in a d-dimensional setting, where d is any
positive integer. We show that among all polygons and convex polyhedra in
d-dimensional space exactly those with rational corner points are encodable
as finite automata.
In the course of proving this we show that the set of images encodable as
finite automata is closed under rational affine transformations.
Several properties of images encodable as finite automata are consequences
of this result. Finally we show that many simple geometric figures such as
circles and parabolas are not encodable as finite automata.2009-04-162009-04-162004-04Technical ReportCDMTCS Research Reports CDMTCS-237 (2004)1178-3540http://hdl.handle.net/2292/3744CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38482012-02-02T23:23:14Zcom_2292_122col_2292_3508Context-Aware Adaptation. A Case Study on Mathematical NotationsMüller, CKohlhase, MIn the last two decades, the World Wide Web has become the universal, and – for many users – main information source. Search engines can efficiently serve daily life
information needs due to the enormous redundancy of relevant resources on the web. For
educational – and even more so for scientific information needs, the web functions much
less efficiently: Scientific publishing is built on a culture of unique reference publications,
and moreover abounds with specialized structures, such as technical nomenclature, notational
conventions, references, tables, or graphs. Moreover, many of these structures are
peculiar to specialized communities determined by nationality, research group membership,
or adherence to a special school of thought. To keep the much-lamented “digital
divide" from becoming a “cultural divide", we have to make online material more accessible
and adaptable to individual users.
In this paper we attack this goal for the field of mathematics where knowledge is
abstract, highly structured, and extraordinarily interlinked. Modern, content-based representation
formats like OpenMath or content MathML allow us to capture, model,
relate, and represent mathematical knowledge objects and thus make them context-aware
and machine-adaptable to the respective user contexts. Building on previous work which
can make mathematical notations adaptable we employ user modeling techniques to make
them adaptive to relieve the reader of configuration tasks. We present a comprehensive
framework for adaptive notation management and evaluate it on an implementation
integrated in the e-learning platform panta rhei.2009-04-162009-04-162008-11Technical ReportCDMTCS Research Reports CDMTCS-341 (2008)1178-3540http://hdl.handle.net/2292/3848CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37752012-02-02T23:23:16Zcom_2292_122col_2292_3508Quantum Theory Looks at Time TravelGreenberger, D.MSvozil, KWe introduce a quantum mechanical model of time travel which includes two figurative beam splitters in
order to induce feedback to earlier times. This leads to a unique solution to the paradox where one could kill
one’s grandfather in that once the future has unfolded, it cannot change the past, and so the past becomes
deterministic. On the other hand, looking forwards towards the future is completely probabilistic. This
resolves the classical paradox in a philosophically satisfying manner.2009-04-162009-04-162005-06Technical ReportCDMTCS Research Reports CDMTCS-268 (2005)1178-3540http://hdl.handle.net/2292/3775CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36602012-02-02T23:23:14Zcom_2292_122col_2292_3508Supplemental Abstracts for DMTCS01Calude, C.SDinneen, MichaelSburlan, SThese 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.2009-04-162009-04-162001-04Technical ReportCDMTCS Research Reports CDMTCS-152 (2001)1178-3540http://hdl.handle.net/2292/3660CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36632012-02-02T23:23:18Zcom_2292_122col_2292_3508Finding a State in a HaystackDonath, NSvozil, KWe 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.2009-04-162009-04-162001-05Technical ReportCDMTCS Research Reports CDMTCS-155 (2001)1178-3540http://hdl.handle.net/2292/3663CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37192012-02-02T23:23:13Zcom_2292_122col_2292_3508Complexity and RandomnessTerwijn, S.A[no abstract available]2009-04-162009-04-162003-03Technical ReportCDMTCS Research Reports CDMTCS-212 (2003)1178-3540http://hdl.handle.net/2292/3719CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36262012-02-02T23:23:16Zcom_2292_122col_2292_3508A Glimpse into Natural ComputingCalude, C.SPaun, GTataram, MonicaWe 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.2009-04-162009-04-161999-12Technical ReportCDMTCS Research Reports CDMTCS-117 (1999)1178-3540http://hdl.handle.net/2292/3626CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37762012-02-02T23:23:12Zcom_2292_122col_2292_3508Characterization of Quantum Computable Decision Problems by State DiscriminationSvozil, KOne advantage of quantum algorithms over classical computation is the possibility to spread out, process, analyse
and extract information in multipartite configurations in coherent superpositions of classical states. This will be discussed
in terms of quantum state identification problems based on a proper partitioning of mutually orthogonal sets of states. The
question arises whether or not it is possible to encode equibalanced decision problems into quantum systems, so that a single
invocation of a filter used for state discrimination suffices to obtain the result.2009-04-162009-04-162005-06Technical ReportCDMTCS Research Reports CDMTCS-269 (2005)1178-3540http://hdl.handle.net/2292/3776CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36412012-02-02T23:23:15Zcom_2292_122col_2292_3508The Poincare-Hardy Inequality on the Complement of a Cantor SetCalude, C.SPavlov, BThe Poincaré–Hardy inequality [see pdf for formula] is derived in R3 on the complement of a Cantor set E. We use a special self-similar tiling and a natural
metric on the space of trajectories generated by a Mauldin–Williams graph which is homeomorphic
with the space of tiles endowed with the Euclidean distance. A crude estimation of the constant K2
is 2,100. Two applications will be briefly discussed. In the last one, the constant K−1 ≈ 0.021819
plays the role of an estimate for the dimensionless Plank constant in the corresponding uncertainty
principle.2009-04-162009-04-162000-05Technical ReportCDMTCS Research Reports CDMTCS-132 (2000)1178-3540http://hdl.handle.net/2292/3641CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38682012-02-02T23:23:14Zcom_2292_122col_2292_3508Three Criteria for Quantum Random Number Generators Based on Beam SplittersSvozil, KWe propose three criteria for the generation of random digital strings from quantum beam splitters: (i)
three or more mutually exclusive outcomes corresponding to the invocation of three- and higher dimensional
Hilbert spaces; (ii) the mandatory use of pure states in conjugated bases for preparation and detection; and
(iii) the use of entangled singlet (unique) states for elimination of bias.2009-04-162009-04-162009-04Technical ReportCDMTCS Research Reports CDMTCS-362 (2009)1178-3540http://hdl.handle.net/2292/3868CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38192012-02-02T23:23:15Zcom_2292_122col_2292_3508On Universal Computably Enumerable Prefix CodesCalude, C.SStaiger, LWe study computably enumerable (c.e.) prefix codes which are capable
of coding all positive integers in an optimal way up to a fixed constant:
these codes will be called universal. We prove various characterisations of
these codes including the following one: a c.e. prefix code is universal iff
it contains the domain of a universal self-delimiting Turing machine. Finally,
we study various properties of these codes from the points of view of
computability, maximality, and density.2009-04-162009-04-162007-10Technical ReportCDMTCS Research Reports CDMTCS-312 (2007)1178-3540http://hdl.handle.net/2292/3819CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37462012-02-02T23:23:14Zcom_2292_122col_2292_3508On Partial RandomnessCalude, C.SStaiger, LTerwijn, S.A[no abstract available]2009-04-162009-04-162004-04Technical ReportCDMTCS Research Reports CDMTCS-239 (2004)1178-3540http://hdl.handle.net/2292/3746CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36062012-02-02T23:23:17Zcom_2292_122col_2292_3508Unstable Dynamics on a Markov Background and Stability in AverageKraegeloh, A.MDynamical systems which switch between several di erent branches or modes of evolution
via a Markov process are simple mathematical models for irreversible systems. The
averaged evolution for such a dynamics can be obtained by a compression of the corresponding
reversible dynamics onto a coinvariant subspace in the sense of the Lax/Phillips
Scattering Scheme.
If the dynamics switches between some stable modes of evolution and some unstable
modes, still the averaged or expectation evolution might be stable. From the theory
of random evolutions the generator A of the averaged evolution is obtained, and a
de nition of stability in average is suggested. With regard to this context the generator
A is investigated and conditions for stability in average are given for certain special
situations. Based on these results, a conjecture is made about su cient and necessary
conditions for stability in average for some more general cases.
In order to nd hints how to verify or how to modify the conjecture three qualitatively
di erent solvable models are studied. Here the spectral properties of the generators of
all three models are studied, and the results are put in relation to the conjecture.2009-04-162009-04-161999-03Technical ReportCDMTCS Research Reports CDMTCS-097 (1999)1178-3540http://hdl.handle.net/2292/3606CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35952012-02-02T23:23:15Zcom_2292_122col_2292_3508A Note on Pseudorandom GeneratorsCalude, C.SMerkle, WWang, YThe concept of pseudorandomness plays an important role in cryptography. In this note we contrast the notions of complexity-theoretic pseudorandom strings (from algorithmic information theory) and pseudorandom strings (from cryptography). For example, we show that we can easily distinguish a complexity-theoretic pseudorandom ensemble from the uniform ensemble. Both notions of pseudorandom strings are uniformly unpredictable; in contrast with pseudorandom strings, complexity-theoretic pseudorandom strings are not polynomial-time unpredictable.2009-04-162009-04-161998-05Technical ReportCDMTCS Research Reports CDMTCS-086 (1998)1178-3540http://hdl.handle.net/2292/3595CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37452012-02-02T23:23:16Zcom_2292_122col_2292_3508The min-max Principle Generalizes Tsirelson's BoundFilipp, SSvozil, KBounds 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.2009-04-162009-04-162004-04Technical ReportCDMTCS Research Reports CDMTCS-238 (2004)1178-3540http://hdl.handle.net/2292/3745CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38182012-02-02T23:23:16Zcom_2292_122col_2292_3508Design and Evaluation of Slicing ObfuscationDrape, SMajumdar, AThe 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.2009-04-162009-04-162007-06Technical ReportCDMTCS Research Reports CDMTCS-311 (2007)1178-3540http://hdl.handle.net/2292/3818CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36882012-02-02T23:23:17Zcom_2292_122col_2292_3508Passages of ProofCalude, C.SCalude, EMarcus, SIn 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.2009-04-162009-04-162002-02Technical ReportCDMTCS Research Reports CDMTCS-180 (2002)1178-3540http://hdl.handle.net/2292/3688CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37202012-02-02T23:23:13Zcom_2292_122col_2292_3508Randomness Relative to Cantor ExpansionsCalude, C.SStaiger, LSvozil, KImagine 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.2009-04-162009-04-162003-04Technical ReportCDMTCS Research Reports CDMTCS-213 (2003)1178-3540http://hdl.handle.net/2292/3720CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38462012-02-02T23:23:17Zcom_2292_122col_2292_3508Simplicity via Provability for Universal Prefix-free Turing MachinesCalude, C.SUniversality is one of the most important ideas in computability theory.
There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This
criterion is more complex than it may appear at a first glance. In this note we
review recent results in Algorithmic Information Theory and propose three
new criteria of simplicity for universal prefix-free Turing machines. These
criteria refer to the possibility of proving various natural properties of such
a machine (its universality, for example) in a formal theory, PA or ZFC. In
all cases some, but not all, machines are simple.2009-04-162009-04-162008-11Technical ReportCDMTCS Research Reports CDMTCS-339 (2008)1178-3540http://hdl.handle.net/2292/3846CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38132012-02-02T23:23:14Zcom_2292_122col_2292_3508Quantum Informatics and the Relations Between Informatics, Physics and Mathematics: A DialogueCalude, C.SGruska, J[no abstract available]2009-04-162009-04-162007-05Technical ReportCDMTCS Research Reports CDMTCS-306 (2007)1178-3540http://hdl.handle.net/2292/3813CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35452012-02-02T23:23:14Zcom_2292_122col_2292_3508Embedding Quantum Universes into Classical OnesCalude, C.SHertling, P.HSvozil, KDo 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.2009-04-162009-04-161997-05Technical ReportCDMTCS Research Reports CDMTCS-036 (1997)1178-3540http://hdl.handle.net/2292/3545CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37942012-02-02T23:23:16Zcom_2292_122col_2292_3508Probability Calculations Under the IAC HypothesisPritchard, GWilson, MarkWe 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.2009-04-162009-04-162006-10Technical ReportCDMTCS Research Reports CDMTCS-287 (2006)1178-3540http://hdl.handle.net/2292/3794CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38142020-03-10T02:14:36Zcom_2292_122col_2292_3508Asymptotics of Diagonal Coefficients of Multivariate Generating FunctionsRaichev, AWilson, MarkThis article presents some recent progress in the asymptotics of diagonal coefficients
of multivariate generating functions and can be seen as an extension of [RW].2009-04-162009-04-162007-05Technical ReportCDMTCS Research Reports CDMTCS-307 (2007)1178-3540http://hdl.handle.net/2292/3814CDMTCS Research Report Series283686233https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35902012-02-02T23:23:18Zcom_2292_122col_2292_3508On Hypersimple Sets and Chaitin ComplexityArslanov, AIn 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.2009-04-162009-04-161998-04Technical ReportCDMTCS Research Reports CDMTCS-081 (1998)1178-3540http://hdl.handle.net/2292/3590CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36662012-02-02T23:23:17Zcom_2292_122col_2292_3508Relations Between the Low Subrecursion ClassesGrozea, C[no abstract available]2009-04-162009-04-162001-07Technical ReportCDMTCS Research Reports CDMTCS-158 (2001)1178-3540http://hdl.handle.net/2292/3666CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35472012-02-02T23:23:13Zcom_2292_122col_2292_3508A Constructive Proof of Gleason's TheoremRichman, FBridges, D.SGleason's theorem states that any totally additive measure on the closed subspaces,
or projections, of a Hilbert space of dimension greater than two is given by a positive
operator of trace class. In this paper we give a constructive proof of that theorem.
A measure μ on the projections of a real or complex Hilbert space assigns to
each projection P a nonnegative real number μ(P) such that if σ = ∑Pi, where the
Pi are mutually orthogonal, then μ(σ) =∑μ(Pi). Such a measure is determined by
its values on the one-dimensional projections. Let W be the measure of the identity
projection, and Px the projection onto the 1-dimensional space spanned by the unit
vector x. Then the measure μ is determined by the real-valued function f(x) = μ(Px)
on the unit sphere, a function which has the property that [see pdf for formula] for each orthonormal basis E. Gleason calls such a function f a frame function of
weight W. If T is a positive operator of trace class, then f(x) = ‹Tx,x› is a frame
function. Gleason's theorem is that every frame function arises in this way.
The original reference for Gleason's theorem is [4], which can also be found in
Hooker [6]. Cooke, Keane and Moran [3] gave a proof that is elementary in the sense
that it does not appeal to the theory of representations of the orthogonal group,
which the original proof does. However, some of the reasoning in [3] seems hopelessly
nonconstructive, so we follow the general outline of [4] until we come to the end of
the 3-dimensional real case, at which point we modify some arguments in [3] rather
than attempt a constructive development of the necessary representation theory.
Any Hermitian form B on a finite-dimensional inner product space gives rise to a
frame function f(x) = B(x; x) whose weight is equal to the trace of the matrix of B.
The essence of Gleason's theorem is the following converse. -- from Introduction2009-04-162009-04-161997-05Technical ReportCDMTCS Research Reports CDMTCS-038 (1997)1178-3540http://hdl.handle.net/2292/3547CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36692012-02-02T23:23:17Zcom_2292_122col_2292_3508The Bridge Crossing Problem: Draft FormCalude, C.SCalude, EIn this note we solve the general case of the Bridge Crossing Problem.2009-04-162009-04-162001-09Technical ReportCDMTCS Research Reports CDMTCS-161 (2001)1178-3540http://hdl.handle.net/2292/3669CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35992012-02-02T23:23:13Zcom_2292_122col_2292_3508Degree-Theoretic Aspects of Computably Enumerable RealsCalude, C.SColes, R.JHertling, P.HKhoussainov, BA 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 α.2009-04-162009-04-161998-09Technical ReportCDMTCS Research Reports CDMTCS-090 (1998)1178-3540http://hdl.handle.net/2292/3599CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37502012-02-02T23:23:15Zcom_2292_122col_2292_3508Inexpensive Linear-Optical Implementations of Deutsch's AlgorithmStay, MDeutsch’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.2009-04-162009-04-162004-07Technical ReportCDMTCS Research Reports CDMTCS-243 (2004)1178-3540http://hdl.handle.net/2292/3750CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37142012-02-02T23:23:14Zcom_2292_122col_2292_3508Games on Graphs: Automata, Structure, and ComplexityKhoussainov, BKowalski, TMcNaughton 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 Introduction2009-04-162009-04-162003-01Technical ReportCDMTCS Research Reports CDMTCS-207 (2003)1178-3540http://hdl.handle.net/2292/3714CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35482012-02-02T23:23:16Zcom_2292_122col_2292_3508A Genius' Story: Two Books on GodelCalude, C.SUndoubtly, 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 mystery2009-04-162009-04-161997-06Technical ReportCDMTCS Research Reports CDMTCS-039 (1997)1178-3540http://hdl.handle.net/2292/3548CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36232012-02-02T23:23:13Zcom_2292_122col_2292_3508Chaitin $\Omega$ Numbers, Solovay Machines, and IncompletenessCalude, C.SComputably 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.2009-04-162009-04-161999-10Technical ReportCDMTCS Research Reports CDMTCS-114 (1999)1178-3540http://hdl.handle.net/2292/3623CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37672012-02-02T23:23:17Zcom_2292_122col_2292_3508Quasi-Apartness and Neighbourhood SpacesIshihara, HMines, RSchuster, PVita, L.SWe extend the concept of apartness spaces to the concept of quasi-apartness spaces. We show that there is an adjunction between the category of quasi-apartness spaces and the category of neighbourhood spaces, which indicates that quasi-apartness is a more natural concept than apartness. We also show that there is an adjoint equivalence between the category of apartness spaces and the category of Grayson’s separated spaces.2009-04-162009-04-162005-03Technical ReportCDMTCS Research Reports CDMTCS-260 (2005)1178-3540http://hdl.handle.net/2292/3767CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37532012-02-02T23:23:13Zcom_2292_122col_2292_3508Computing with Cells and Atoms: After Five YearsCalude, C.SPaun, GThis 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.2009-04-162009-04-162004-08Technical ReportCDMTCS Research Reports CDMTCS-246 (2004)1178-3540http://hdl.handle.net/2292/3753CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36922012-02-02T23:23:17Zcom_2292_122col_2292_3508n-ary Quantum Information Defined by State PartitionsSvozil, KWe define a measure of quantum information which is based on state partitions. Properties of this measure for entangled
many-particle states are discussed. k particles specify k “nits” in such a way that k mutually commuting measurements of
n-ary observables are necessary to determine the information.2009-04-162009-04-162002-05Technical ReportCDMTCS Research Reports CDMTCS-184 (2002)1178-3540http://hdl.handle.net/2292/3692CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37482012-02-02T23:23:17Zcom_2292_122col_2292_3508Is Complexity a Source of Incompleteness?Calude, C.SJuergensen, HIn this paper we prove Chaitin’s “heuristic principle”, the theorems of a finitelyspecified
theory cannot be significantly more complex than the theory itself, for an appropriate
measure of complexity. We show that the measure is invariant under the change
of the G¨odel numbering. For this measure, the theorems of a finitely-specified, sound,
consistent theory strong enough to formalize arithmetic which is arithmetically sound
(like Zermelo-Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity,
hence every sentence of the theory which is significantly more complex than the
theory is unprovable. Previous results showing that incompleteness is not accidental, but
ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence
of length n is provable in the theory tends to zero when n tends to infinity, while the
probability that a sentence of length n is true is strictly positive.2009-04-162009-04-162004-06Technical ReportCDMTCS Research Reports CDMTCS-241 (2004)1178-3540http://hdl.handle.net/2292/3748CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35972020-03-09T01:54:14Zcom_2292_122col_2292_3508The Hausdorff Measure of Regular Omega-Languages is ComputableStaiger, LIn several previous papers we have shown how to calculate Hausdor
dimension and measure for certain classes of regular ω-languages
(cf. [MS94], [St89], and [St93]). In this note we show that the results obtained in the papers [MS94] and [St93] can be used to give
an effective procedure for the calculation of the Hausdor
measure for
arbitrary regular ω-languages.2009-04-162009-04-161998-08Technical ReportCDMTCS Research Reports CDMTCS-088 (1998)1178-3540http://hdl.handle.net/2292/3597CDMTCS Research Report Series33898https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35942012-02-02T23:23:15Zcom_2292_122col_2292_3508Search and Enumeration Techniques for Incidence StructuresDenny, P.CThis thesis investigates a number of probabilistic and exhaustive computational search
techniques for the construction of a wide variety of combinatorial designs, and in particular,
incidence structures. The emphasis is primarily from a computer science perspective, and
focuses on the algorithmic development of the techniques, taking into account running time
considerations and storage requirements. The search and enumeration techniques developed
in this thesis have led to the discovery of a number of new results in the field of
combinatorial design theory.2009-04-162009-04-161998-05Technical ReportCDMTCS Research Reports CDMTCS-085 (1998)1178-3540http://hdl.handle.net/2292/3594CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36942012-02-02T23:23:13Zcom_2292_122col_2292_3508Implementing Bead--Sort with P systemsArulanandham, J.JIn this paper, we implement Bead-Sort, a natural sorting algorithm we introduced in [1], with the new, biochemically inspired P systems. We make use of a special type of P system – a tissue P system that computes by means of communication (using symport/antiport rules) only.2009-04-162009-04-162002-05Technical ReportCDMTCS Research Reports CDMTCS-186 (2002)1178-3540http://hdl.handle.net/2292/3694CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35722012-02-02T23:23:13Zcom_2292_122col_2292_3508Disjunctive Sequences: An OverviewCalude, C.SPriese, LStaiger, LFollowing 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.2009-04-162009-04-161997-10Technical ReportCDMTCS Research Reports CDMTCS-063 (1997)1178-3540http://hdl.handle.net/2292/3572CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36892012-02-02T23:23:13Zcom_2292_122col_2292_3508Computable Isomorphism of Boolean Algebras with OperatorsKhoussainov, BKowalski, TOne of the central topics in computable algebra and model theory is concerned with the study of
computable isomorphisms. Classically, we do not distinguish between isomorphic structures, however, from
computability point of view, isomorphic structures can differ quite dramatically. A typical example is
provided by the linear order of type ω. It has two computable copies such that in one the successor function
is computable, but it is not computable in the other. These are clearly classically isomorphic, but they are
not computably isomorphic.2009-04-162009-04-162002-03Technical ReportCDMTCS Research Reports CDMTCS-181 (2002)1178-3540http://hdl.handle.net/2292/3689CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35262012-02-02T23:23:14Zcom_2292_122col_2292_3508Randomness, Computability, and Algebraic SpecificationsKhoussainov, B[no abstract available]2009-04-162009-04-161996-08Technical ReportCDMTCS Research Reports CDMTCS-017 (1996)1178-3540http://hdl.handle.net/2292/3526CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37252012-02-02T23:23:15Zcom_2292_122col_2292_3508Generalisations of Disjunctive SequencesCalude, C.SStaiger, LThe 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.2009-04-162009-04-162003-06Technical ReportCDMTCS Research Reports CDMTCS-218 (2003)1178-3540http://hdl.handle.net/2292/3725CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36392012-02-02T23:23:17Zcom_2292_122col_2292_3508Reflections on Quantum ComputingCalude, C.SDinneen, MichaelSvozil, KIn this rather speculative note three problems pertaining to the power
and limits of quantum computing are posed and partially answered: a)
when are quantum speedups possible?, b) is fixed-point computing a better
model for quantum computing?, c) can quantum computing trespass
the Turing barrier?2009-04-162009-04-162000-03Technical ReportCDMTCS Research Reports CDMTCS-130 (2000)1178-3540http://hdl.handle.net/2292/3639CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36872012-02-02T23:23:17Zcom_2292_122col_2292_3508Logical Equivalence Between Generalized Urn Models and Finite AutomataSvozil, KTo every generalized urn model there exists a finite (Mealy) automaton with identical
propositional calculus. The converse is true as well.2009-04-162009-04-162002-02Technical ReportCDMTCS Research Reports CDMTCS-179 (2002)1178-3540http://hdl.handle.net/2292/3687CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35652012-02-02T23:23:16Zcom_2292_122col_2292_3508Paradise Lost, or Paradise Regained?Bridges, D.SDediu, L.SThis paper outlines some of the history and philosophy of constructive mathematics, concentrating on the work of the late Errett Bishop and his followers.2009-04-162009-04-161997-09Technical ReportCDMTCS Research Reports CDMTCS-056 (1997)1178-3540http://hdl.handle.net/2292/3565CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35402012-02-02T23:23:13Zcom_2292_122col_2292_3508Computable Isomorphisms, Degree Spectra of Relations, and Scott FamiliesKhoussainov, BShore, R.AIn studying effective structures we investigate the effective content of typical notions and
constructions in many branches of mathematics including universal algebra and model theory.
In particular, we are interested in the possibilities of effectivizing model-theoretic or algebraic
constructions and the limits on these possibilities. For instance, we try to understand whether
certain results of model theory (or universal algebra) can be carried out effectively. If not,
we then try to discover sharp effective counterexamples.
The systematic study of effectiveness in algebraic structures goes back to pioneering
papers by Frölich and Shepherdson [11], Malcev [28][29], and Rabin [34] in the early 60s.
Later in the early 70s, Nerode and his collaborators initiated combining algebraic constructions
with priority arguments from computability theory thus beginning a new era in the
development of the subject.
Nowadays, there various approaches to effectiveness in structures. For example, Cenzer,
Nerode, Remmel have been developing theory of p-time structures [6]. Khoussainov and
Nerode have began the development of the theory of automatic structures [27]. In this paper
we are interested in those structures in which the basic computations can be performed by
Turing machines.2009-04-162009-04-161997-04Technical ReportCDMTCS Research Reports CDMTCS-031 (1997)1178-3540http://hdl.handle.net/2292/3540CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36682012-02-02T23:23:17Zcom_2292_122col_2292_3508LifeTime: A Unified Study of Life (A Preliminary Version)Meyerstein, F.WMoller, A.P[no abstract available]2009-04-162009-04-162001-09Technical ReportCDMTCS Research Reports CDMTCS-160 (2001)1178-3540http://hdl.handle.net/2292/3668CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37522012-02-02T23:23:19Zcom_2292_122col_2292_3508Fitting Parameters for a Solvable Model of a Quantum Network (CDMTCS)Harmer, M.A solvable model corresponding to a given quantum network is
described in [22] without an explicit description of how to fit the parameters
of the solvable model. Here we give a procedure to fit these
parameters so that the solvable model reproduces the important features,
viz. the scattering matrix for the physically relevant energies, of
the quantum network, subject to the non-vanishing of a determinant.2009-04-162009-04-162004-07Technical ReportCDMTCS Research Reports CDMTCS-245 (2004)1178-3540http://hdl.handle.net/2292/3752CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36112012-02-02T23:23:16Zcom_2292_122col_2292_3508P Systems with Active Membranes: Attacking NP Complete ProblemsPaun, GP systems are parallel Molecular Computing models based on processing multisets of objects in cell-like membrane structures. Various variants were already
shown to be computationally universal, equal in power to Turing machines. In this
paper one proposes a class of P systems whose membranes are the main active
components, in the sense that they directly mediate the evolution and the communication of objects. Moreover, the membranes can multiply themselves by division.
We prove that this variant is not only computationally universal, but also able to
solve NP complete problems in polynomial (actually, linear) time. We exemplify
this assertion with the well-known SAT problem.2009-04-162009-04-161999-05Technical ReportCDMTCS Research Reports CDMTCS-102 (1999)1178-3540http://hdl.handle.net/2292/3611CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37152012-02-02T23:23:13Zcom_2292_122col_2292_3508Automatic linear orders and trees (Revised)Khoussainov, BRubin, SStephan, FWe investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to Cantor-Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular we show that every infinite path in an automatic tree with countably many infinite paths is a regular language.2009-04-162009-04-162003-11Technical ReportCDMTCS Research Reports CDMTCS-208 (2003)1178-3540http://hdl.handle.net/2292/3715CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36812012-02-02T23:23:17Zcom_2292_122col_2292_3508Some Computability-Theoretical Aspects of Reals and RandomnessDowney, R.GWe study computably enumerable reals (i.e. their left cut is computably
enumerable) in terms of their spectra of representations and presentations. Then we study
such objects in terms of algorithmic randomness, culminating in some recent work of the
author with Hirschfeldt, Laforte, and Nies concerning methods of calibrating randomness.2009-04-162009-04-162002-01Technical ReportCDMTCS Research Reports CDMTCS-173 (2002)1178-3540http://hdl.handle.net/2292/3681CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37262012-02-02T23:23:13Zcom_2292_122col_2292_3508Dialogues on Quantum ComputingCalude, C.SWhat 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.2009-04-162009-04-162003-06Technical ReportCDMTCS Research Reports CDMTCS-219 (2003)1178-3540http://hdl.handle.net/2292/3726CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35782012-02-02T23:23:13Zcom_2292_122col_2292_3508Adjoints, Absolute Values and Polar DecompostionsBridges, D.SRichman, FSchuster, PVarious questions about adjoints, absolute values and polar
decompositions of operators are addressed from a constructive point of view.
The focus is on bilinear forms. Conditions are given for the existence of an
adjoint, and a general notion of a polar decomposition is developed. The Riesz
representation theorem is proved without countable choice.2009-04-162009-04-161997-11Technical ReportCDMTCS Research Reports CDMTCS-069 (1997)1178-3540http://hdl.handle.net/2292/3578CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36122012-02-02T23:23:13Zcom_2292_122col_2292_3508Variable-Length Codes for Sources with Equiprobable SymbolsAssanovich, BGunther, UlrichVariable-length codes can provide compression for data communication. Such codes may be
used not only when the source statistics is known but also when we do not know the source
probability distribution, and a source with equal symbol probabilities (equiprobable symbols)
can or has to be assumed. This paper presents variable-length codes with code words that differ
in length by at most one code symbol. Such codes suit the efficient encoding of sources with
equiprobable symbols. We accommodate non-binary codes and present an iterative algorithm
for the construction of such codes. We also calculate the average codeword length for such
codes, which extends Krichevski's result for binary codes [5]. Finally, we propose a scheme that
allows the code to be communicated efficiently from transmitter to receiver.2009-04-162009-04-161999-05Technical ReportCDMTCS Research Reports CDMTCS-103 (1999)1178-3540http://hdl.handle.net/2292/3612CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/36212012-02-02T23:23:15Zcom_2292_122col_2292_3508Solving Problems with Finite Test SetsCalude, C.SJuergensen, HLegg, SEvery finite and every co-finite set of non-negative integers is decidable. This is
true and it is not, depending on whether the set is given constructively. A similar
constraint is applicable in language theory and many other fields. The constraint is
usually understood and, hence, omitted.
The phenomenon of a set being finite, but possibly undecidable, is, of course,
a consequence of allowing non-constructive arguments in proofs. In this note we
discuss a few ramifications of this fact. We start out with showing that every number
theoretic statement that can be expressed in first-order logic can be reduced to a finite set, to be called a test set. Thus, if one knew the test set, one could determine
the truth of the statement. The crucial point is, of course, that we may not able to
know what the finite test set is. Using problems in the class II1 of the arithmetic
hierarchy as an example, we establish that the bound on the size of the test set is
Turing-complete and that it is upper-bounded by the busy-beaver function.
This re-enforces the fact that there is a vast difference between finiteness and
constructive finiteness. In the context of the present re-opened discussion about the
notion of computability – possibly extending its realm through new computational
models derived from physics – the constraint of constructivity of the model itself
may add another twist.2009-04-162009-04-161999-09Technical ReportCDMTCS Research Reports CDMTCS-112 (1999)1178-3540http://hdl.handle.net/2292/3621CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38212012-02-02T23:23:13Zcom_2292_122col_2292_3508The Underlying Optimal Protocol of Rule 218 Cellular AutomatonGoles, ELittleland, CedricRapaport, I2009-04-162009-04-162007-11Technical ReportCDMTCS Research Reports CDMTCS-314 (2007)1178-3540http://hdl.handle.net/2292/3821CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/37402012-02-02T23:23:15Zcom_2292_122col_2292_3508Quantum Information via State Partitions and the Context Transition PrincipleSvozil, KFor many–particle systems, quantum information in base n can be defined by
partitioning the set of states according to the outcomes of n–ary (joint) observables.
Thereby, k particles can carry k nits. With regards to the randomness of single
outcomes, a context translation principle is proposed. Quantum randomness is
related to the uncontrollable degrees of freedom of the measurement interface,
thereby translating a mismatch between the state prepared and the state measured.2009-04-162009-04-162004-01Technical ReportCDMTCS Research Reports CDMTCS-233 (2004)1178-3540http://hdl.handle.net/2292/3740CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/35282012-02-02T23:23:14Zcom_2292_122col_2292_3508Forbidden Minors to Graphs with Small Feedback SetsDinneen, MichaelCattell, KFellows, M.RFinite obstruction set characterizations for lower ideals in the minor order are guaran-
teed to exist by the Graph Minor Theorem. In this paper we characterize several families of
graphs with small feedback sets, namely k
1-Feedback Vertex Set, k
2-Feedback Edge
Set and (k
1,k
2){Feedback Vertex/Edge Set, for small integer parameters k
1 and k
2.
Our constructive methods can compute obstruction sets for any minor-closed family of
graphs, provided the pathwidth (or treewidth) of the largest obstruction is known.2009-04-162009-04-161996-10Technical ReportCDMTCS Research Reports CDMTCS-019 (1996)1178-3540http://hdl.handle.net/2292/3528CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38352012-02-02T23:23:15Zcom_2292_122col_2292_3508Every Computably Enumerable Random Real Is Provably Computably Enumerable RandomCalude, C.SHay, N.JWe prove that every computably enumerable (c.e.) random real is provable in
Peano Arithmetic (PA) to be c.e. random, a statement communicated to one author
by B. Solovay. A major step in the proof is to show that the theorem stating that “a
real is c.e. and random iff it is the halting probability of a universal prefix-free Turing
machine" can be proven in PA. Our proof, which is simpler than the standard one, can
also be used for the original theorem.
The result that every c.e. random real is provably c.e. random is in contrast with
the case of computable functions, where not every computable function is provably
computable. It is even more interesting to compare this result with the fact that – in general – random finite strings are not provably random.
The paper also includes a sharper form of the Kraft-Chaitin Theorem, as well as an
automatic proof of this theorem written with the interactive theorem prover Isabelle.2009-04-162009-04-162008-07Technical ReportCDMTCS Research Reports CDMTCS-328 (2008)1178-3540http://hdl.handle.net/2292/3835CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38362012-02-02T23:23:19Zcom_2292_122col_2292_3508A New Linear-Time Dominating Number Algorithm for Graphs of Bounded PathwidthDinneen, MichaelFenton, A.J.LWe present a simple algorithm for determining the minimum dominating
number of any graph of bounded pathwidth. The algorithm has running time
O(3t+1n) where n is the size of the graph and t is a fixed pathwidth bound.
We also present an implementation in Python of this algorithm extended to
handle graphs of bounded treewidth.2009-04-162009-04-162008-07Technical ReportCDMTCS Research Reports CDMTCS-329 (2008)1178-3540http://hdl.handle.net/2292/3836CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandoai:researchspace.auckland.ac.nz:2292/38052012-02-02T23:23:15Zcom_2292_122col_2292_3508Prefix-free Lukasiewicz LanguagesStaiger, LGeneralised Łukasiewicz languages are simply described languages having
good information-theoretic properties. An especially desirable property is
the one of being a prefix code. This paper addresses the question under which
conditions a generalised Łukasiewicz language is a prefix code. Moreover, an
upper bound on the delay of decipherability of a generalised Łukasiewicz language
is derived.2009-04-162009-04-162007-01Technical ReportCDMTCS Research Reports CDMTCS-298 (2007)1178-3540http://hdl.handle.net/2292/3805CDMTCS Research Report Serieshttps://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmThe author(s)http://purl.org/eprint/accessRights/OpenAccessDepartment of Computer Science, The University of Auckland, New Zealandetdms///col_2292_3508/100