Cristian S. Calude

TCS Journal 2024 Journal Article

How real is incomputability in physics?

• José Manuel Agüero Trejo
• Cristian S. Calude
• Michael J. Dinneen
• Arkady Fedorov
• Anatoly Kulikov
• Rohit Navarathna
• Karl Svozil

A physical system is determined by a finite set of initial conditions and “laws” represented by equations. The system is computable if we can solve the equations in all instances using a “finite body of mathematical knowledge”. In this case, if the laws of the system can be coded into a computer program, then given the initial conditions of the system, one can compute the system's evolution. Are there incomputable physical systems? This question has been theoretically studied in the last 30–40 years. In this paper, we experimentally show for the first time the strong incomputability of a quantum experiment, namely the outputs of a quantum random number generator. Moreover, the experimental results are robust and statistically significant.

TCS Journal 2021 Journal Article

A new quantum random number generator certified by value indefiniteness

• José Manuel Agüero Trejo
• Cristian S. Calude

In this paper we propose a new ternary QRNG based on measuring located value indefinite observables with probabilities 1 / 4, 1 / 2, 1 / 4 and prove that every sequence generated is maximally unpredictable, 3-bi-immune (a stronger form of bi-immunity), and its prefixes are Borel normal. The ternary quantum random digits produced by the QRNG are algorithmically transformed into quantum random bits using an alphabetic morphism which preserves all the above properties.

TCS Journal 2021 Journal Article

Bi-immunity over different size alphabets

• Cristian S. Calude
• Karen Frilya Celine
• Ziyuan Gao
• Sanjay Jain
• Ludwig Staiger
• Frank Stephan

In this paper we study various notions of bi-immunity over alphabets with b ≥ 2 elements and recursive transformations between sequences on different alphabets which preserve them. Furthermore, we extend the study from sequences bounded by a constant to sequences over the alphabet of all natural numbers, which may or may not be bounded by a recursive function, and relate them to the Turing degrees in which they can occur.

TCS Journal 2020 Journal Article

Searching for shortest and least programs

• Cristian S. Calude
• Sanjay Jain
• Wolfgang Merkle
• Frank Stephan

The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U, that is, U ( p ) = x and p is a shortest string with this property. Neither the plain nor the prefix-free version of Kolmogorov complexity are recursive but for both versions it is well-known that there are recursive exact Solovay functions, that is, recursive upper bounds for Kolmogorov complexity that are infinitely often tight. Let a coding function for a machine M be a function f such that f ( x ) is always a program of x for M. From the existence of exact Solovay functions it follows easily that for every universal machine there is a recursive coding function that maps infinitely many strings to a shortest program. Extending a recent line of research, in what follows it is investigated in which situations there is a coding function for some universal machine that maps infinitely many strings to the length-lexicographically least program. The main results which hold in the plain as well as in the prefix-free setting are the following. For every universal machine there is a recursive coding function that maps infinitely many strings to their least programs. There is a partial recursive coding function (defined in the natural way) for some universal machine that for every set maps infinitely many prefixes of the set to their least programs. Exactly for every set that is Bennett shallow (not deep), there is a recursive coding function for some universal machine that maps all prefixes of the set to their least programs. Differences between the plain and the prefix-free frameworks are obtained by considering effective sequences I 1, I 2, … of mutually disjoint finite sets and asking for a recursive coding function for some universal machine that maps at least one string in each set I n to its least code. Such coding functions do not exist in the prefix-free setting but exist in the plain setting in case the sets I n are not too small.

STOC Conference 2017 Conference Paper

Deciding parity games in quasipolynomial time

• Cristian S. Calude
• Sanjay Jain 0001
• Bakhadyr Khoussainov
• Wei Li 0050
• Frank Stephan 0001

TCS Journal 2017 Journal Article

QUBO formulations for the graph isomorphism problem and related problems

• Cristian S. Calude
• Michael J. Dinneen
• Richard Hua

We present and compare various methods to construct efficient QUBO formulations for the Graph Isomorphism Problem—one of a very few problems in NP that is neither known to be solvable in polynomial time nor NP-complete—and two related Subgraph Isomorphism Problems that are NP-hard. Experimental results on two QUBO formulations of the Graph Isomorphism Problem suggest that our direct formulation is more practical than the others with respect to running on the D-Wave architecture.

I&C Journal 2016 Journal Article

Finite state incompressible infinite sequences

• Cristian S. Calude
• Ludwig Staiger
• Frank Stephan

In this paper we define and study finite state complexity of finite strings and infinite sequences as well as connections between these complexity notions to randomness and normality. We show that the finite state complexity does not only depend on the codes for finite transducers, but also on how the codes are mapped to transducers. As a consequence we relate the finite state complexity to the plain (Kolmogorov) complexity, to the process complexity and to prefix-free complexity. Working with prefix-free sets of codes we characterise Martin-Löf random sequences in terms of finite state complexity: the weak power of finite transducers is compensated by the high complexity of enumeration of finite transducers. We also prove that every finite state incompressible sequence is normal, but the converse implication is not true. These results also show that our definition of finite state incompressibility is stronger than all other known forms of finite automata based incompressibility, in particular the notion related to finite automaton based betting systems introduced by Schnorr and Stimm. The paper concludes with a discussion of open questions.

TCS Journal 2012 Journal Article

The complexity of Euler’s integer partition theorem

• Cristian S. Calude
• Elena Calude
• Melissa S. Queen

Euler’s integer partition theorem, which states that the number of partitions of an integer into odd integers is equal to the number of partitions into distinct integers, ranks 16 in Wells’ list of the most beautiful theorems (Wells, 1990) [15]. In this paper, we use the algorithmic method to evaluate the complexity of mathematical statements developed in Calude et al. (2006) [5] and Calude and Calude (2009, 2010) [6, 7] and to show that Euler’s theorem is in class C U, 3, the same complexity class as the Riemann hypothesis.

TCS Journal 2011 Journal Article

Finite state complexity

• Cristian S. Calude
• Kai Salomaa
• Tania K. Roblot

In this paper we develop a version of Algorithmic Information Theory (AIT) based on finite transducers instead of Turing machines; the complexity induced is called finite-state complexity. In spite of the fact that the Universality Theorem (true for Turing machines) is false for finite transducers, the Invariance Theorem holds true for finite-state complexity. We construct a class of finite-state complexities based on various enumerations of the set of finite transducers. In contrast with descriptional complexities (plain, prefix-free) from AIT, finite-state complexity is computable and there is no a priori upper bound for the number of states used for minimal descriptions of arbitrary strings. Upper and lower bounds for the finite-state complexity of arbitrary strings, and for strings of particular types, are given and incompressible strings are studied.

TCS Journal 2011 Journal Article

Simplicity via provability for universal prefix-free Turing machines

• Cristian S. Calude

Universality, provability and simplicity are key notions 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 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, Peano arithmetic or Zermelo–Fraenkel set theory. In all cases some, but not all, machines are simple.

TCS Journal 2011 Journal Article

Universal recursively enumerable sets of strings

• Cristian S. Calude
• André Nies
• Ludwig Staiger
• Frank Stephan

The main topics of the present work are universal machines for plain and prefix-free description complexity and their domains. It is characterised when an r. e. set W is the domain of a universal plain machine in terms of the description complexity of the spectrum function s W mapping each non-negative integer n to the number of all strings of length n in W; furthermore, a characterisation of the same style is given for supersets of domains of universal plain machines. Similarly the prefix-free sets which are domains or supersets of domains of universal prefix-free machines are characterised. Furthermore, it is shown that the halting probability Ω V of an r. e. prefix-free set V containing the domain of a universal prefix-free machine is Martin-Löf random, while V may not be the domain of any universal prefix-free machine itself. Based on these investigations, the question whether every domain of a universal plain machine is the superset of the domain of some universal prefix-free machine is discussed. A negative answer to this question had been presented at CiE 2010 by Mikhail Andreev, Ilya Razenshteyn and Alexander Shen, while this paper was under review.

I&C Journal 2010 Journal Article

Algorithmically independent sequences

• Cristian S. Calude
• Marius Zimand

Two objects are independent if they do not affect each other. Independence is well-understood in classical information theory, but less in algorithmic information theory. Working in the framework of algorithmic information theory, the paper proposes two types of independence for arbitrary infinite binary sequences and studies their properties. Our two proposed notions of independence have some of the intuitive properties that one naturally expects. For example, for every sequence x, the set of sequences that are independent with x has measure one. For both notions of independence we investigate to what extent pairs of independent sequences, can be effectively constructed via Turing reductions (from one or more input sequences). In this respect, we prove several impossibility results. For example, it is shown that there is no effective way of producing from an arbitrary sequence with positive constructive Hausdorff dimension two sequences that are independent (even in the weaker type of independence) and have super-logarithmic complexity. Finally, a few conjectures and open questions are discussed.

TCS Journal 2009 Journal Article

Topology on words

• Cristian S. Calude
• Helmut Jürgensen
• Ludwig Staiger

We investigate properties of topologies on sets of finite and infinite words over a finite alphabet. The guiding example is the topology generated by the prefix relation on the set of finite words, considered as a partial order. This partial order extends naturally to the set of infinite words; hence it generates a topology on the union of the sets of finite and infinite words. We consider several partial orders which have similar properties and identify general principles according to which the transition from finite to infinite words is natural. We provide a uniform topological framework for the set of finite and infinite words to handle limits in a general fashion.

TCS Journal 2007 Journal Article

Preface

• Mark Burgin
• Cristian S. Calude

I&C Journal 2006 Journal Article

Natural halting probabilities, partial randomness, and zeta functions

• Cristian S. Calude
• Michael A. Stay

We introduce the zeta number, natural halting probability, and natural complexity of a Turing machine and we relate them to Chaitin’s Omega number, halting probability, and program-size complexity. A classification of Turing machines according to their zeta numbers is proposed: divergent, convergent, and tuatara. We prove the existence of universal convergent and tuatara machines. Various results on (algorithmic) randomness and partial randomness are proved. For example, we show that the zeta number of a universal tuatara machine is c. e. and random. A new type of partial randomness, asymptotic randomness, is introduced. Finally we show that in contrast to classical (algorithmic) randomness—which cannot be naturally characterised in terms of plain complexity—asymptotic randomness admits such a characterisation.

TCS Journal 2004 Journal Article

A fast natural algorithm for searching

• Joshua J. Arulanandham
• Cristian S. Calude
• Michael J. Dinneen

In 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.

TCS Journal 2002 Journal Article

A characterization of c.e. random reals

• Cristian S. Calude

A real α is computably enumerable if it is the limit of a computable, increasing, converging sequence of rationals. A real α is random if its binary expansion is a random sequence. Our aim is to offer a self-contained proof, based on the papers (Calude et al. , in: M. Morvan, C. Meinel, D. Krob (Eds.), Proc. 15th Symp. on Theoretical Aspects of Computer Science, Paris, Springer, Berlin, 1998, pp. 596–606; Chaitin, J. Assoc. Comput. Mach. 22 (1975) 329; Slaman, manuscript, 14 December 1998, 2 pp. ; Solovay, unpublished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp.), of the following theorem: a real is c. e. and random if and only if it is a Chaitin Ω real, i. e. , the halting probability of some universal self-delimiting Turing machine.

TCS Journal 2002 Journal Article

Chaitin Ω numbers, Solovay machines, and Gödel incompleteness

• Cristian S. Calude

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

TCS Journal 2001 Journal Article

Recursively enumerable reals and Chaitin Ω numbers

• Cristian S. Calude
• Peter H. Hertling
• Bakhadyr Khoussainov
• Yongge Wang

A real α is called recursively enumerable if it is the limit of a recursive, increasing, converging sequence of rationals. Following Solovay (unpublished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp.) and Chaitin (IBM J. Res. Develop. 21 (1977) 350–359, 496.) we say that an r. e. real α dominates an r. e. real β if from a good approximation of α from below one can compute a good approximation of β from below. We shall study this relation and characterize it in terms of relations between r. e. sets. Solovay's (unpublished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp.) Ω-like numbers are the maximal r. e. real numbers with respect to this order. They are random r. e. real numbers. The halting probability of a universal self-delimiting Turing machine (Chaitin's Ω number (J. Assoc. Comput. Mach. 22 (1975) 329–340)) is also a random r. e. real. Solovay showed that any Chaitin Ω number is Ω-like. In this paper we show that the converse implication is true as well: any Ω-like real in the unit interval is the halting probability of a universal self-delimiting Turing machine.

TCS Journal 2000 Journal Article

Finite nondeterministic automata: Simulation and minimality

• Cristian S. Calude
• Elena Calude
• Bakhadyr Khoussainov

Motivated by recent applications of finite automata to theoretical physics, we study the minimization problem for nondeterministic automata (with outputs, but no initial states). We use Ehrenfeucht–Fraı̈sse-like games to model automata responses and simulations. The minimal automaton is constructed and, in contrast with the classical case, proved to be unique up to an isomorphism. Finally, we investigate the partial ordering induced by automata simulations. For example, we prove that, with respect to this ordering, the class of deterministic automata forms an ideal in the class of all automata.

MFCS Conference 1989 Conference Paper

Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A Constructive Glimpse

• Cristian S. Calude
• Dragos Vaida