62 results on '"Calude, Cristian S."'
Search Results
2. Binary Quantum Random Number Generator Based on Value Indefinite Observables.
- Author
-
Calude, Cristian S. and Svozil, Karl
- Subjects
- *
QUANTUM mechanics , *RANDOM numbers , *KOCHEN-Specker theorem , *HILBERT space , *HYPERGRAPHS - Abstract
All quantum random number generators based on measuring value indefinite observables are at least threedimensional because the Kochen-Specker Theorem and the Located Kochen-Specker Theorem are false in dimension two. In this article, we construct a quantum random number generator based on measuring a threedimensional value indefinite observable that generates binary quantum random outputs with the same randomness qualities as the ternary ones: its outputs are maximally unpredictable. [ABSTRACT FROM AUTHOR]
- Published
- 2023
3. Photonic ternary quantum random number generators.
- Author
-
Trejo, José Manuel Agüero and Calude, Cristian S.
- Subjects
- *
RANDOM number generators , *QUANTUM numbers - Abstract
We construct a class of three-dimensional photonic quantum random number generators (QRNGs) and prove that each of them generates maximally unpredictable digits via measurements that are robust to errors. This shows that every sequence generated is strongly incomputable; hence its quality is provably better than that of every pseudo-random sequence. These results suggest that incomputability in physics is real and practically applicable. Finally, we present photonic implementations of three-dimensional QRNGs and discuss device independence. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. What perceptron neural networks are (not) good for?
- Author
-
Calude, Cristian S., Heidari, Shahrokh, and Sifakis, Joseph
- Subjects
- *
QUANTUM annealing , *ARTIFICIAL intelligence , *BOOLEAN functions , *SET functions , *QUANTUM computing , *COMPLEXITY (Philosophy) , *SUCCESS - Abstract
Perceptron Neural Networks (PNNs) are essential components of intelligent systems because they produce efficient solutions to problems of overwhelming complexity for conventional computing methods. Many papers show that PNNs can approximate a wide variety of functions, but comparatively, very few discuss their limitations and the scope of this paper. To this aim, we define two classes of Boolean functions – sensitive and robust –, and prove that an exponentially large set of sensitive functions are exponentially difficult to compute by multi-layer PNNs (hence incomputable by single-layer PNNs). A comparatively large set of functions in the second one, but not all, are computable by single-layer PNNs. Finally, we used polynomial threshold PNNs to compute all Boolean functions with quantum annealing and present in detail a QUBO computation on the D-Wave Advantage. These results confirm that the successes of PNNs, or lack of them, are in part determined by properties of the learned data sets and suggest that sensitive functions may not be (efficiently) computed by PNNs. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. ChatGPT, Randomness and the Infinity.
- Author
-
Calude, Cristian S.
- Subjects
- *
CHATGPT , *ABACUS , *CHATBOTS , *LANGUAGE models , *ARTIFICIAL intelligence - Abstract
ChatGPT, an application first released in November 2022 by Abacus. AI, has become very popular instantaneously and still dominates AI discussions in media and technical circles. In this paper, we briefly discuss the merits and shortcomings of ChatGPT, the role of randomness in its capacity for diversification and a "dialogue" about infinity. We end with a few questions. [ABSTRACT FROM AUTHOR]
- Published
- 2023
6. How real is incomputability in physics?
- Author
-
Agüero Trejo, José Manuel, Calude, Cristian S., Dinneen, Michael J., Fedorov, Arkady, Kulikov, Anatoly, Navarathna, Rohit, and Svozil, Karl
- Subjects
- *
RANDOM number generators , *QUANTUM numbers , *COMPUTER software , *COMPUTER programming , *COMPUTER systems - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
7. Photonic Ternary Quantum Number Generators.
- Author
-
Trejo, José Manuel Agüero and Calude, Cristian S.
- Subjects
- *
QUANTUM numbers , *PHOTONICS , *RANDOM number generators , *ERRORS , *ROBUST control - Abstract
We construct a class of 3-dimensional photonic quantum random number generators and prove that each generates maximally unpredictable digits via measurements that are robust to errors. In particular, every sequence generated is strongly incomputable; hence its quality is provable better than that of every pseudo-random sequence. We also briefly contrast 2-dimensional and 3-dimensional beamsplitters, discuss photonic implementations and show the superiority of the later ones. These results suggest that incomputability in physics is real and practically useful. [ABSTRACT FROM AUTHOR]
- Published
- 2022
8. Bi-immunity over different size alphabets.
- Author
-
Calude, Cristian S., Frilya Celine, Karen, Gao, Ziyuan, Jain, Sanjay, Staiger, Ludwig, and Stephan, Frank
- Subjects
- *
NATURAL numbers , *SIZE - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
9. Long and Short Proofs.
- Author
-
Calude, Cristian S. and Staiger, Ludwig
- Subjects
- *
PROOF theory , *MATHEMATICAL logic , *MATHEMATICAL formulas , *MATHEMATICAL models , *MATHEMATICAL analysis - Abstract
We study the "gap" between the length of a theorem and the smallest length of its proof in a given formal system T. To this aim, we define and study f-short and f-long proofs in T, where f is a computable function. The results show that formalisation comes with a price tag, and a long proof does not guarantee a theorem's non-triviality or importance. Applications to proof-assistants are briefly discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2022
10. A new quantum random number generator certified by value indefiniteness.
- Author
-
Agüero Trejo, José Manuel and Calude, Cristian S.
- Subjects
- *
RANDOM number generators , *QUANTUM numbers , *QUBITS , *RANDOM numbers , *MORPHISMS (Mathematics) , *BOREL sets - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
11. What Neural Networks Are (Not) Good For?
- Author
-
Calude, Cristian S., Heidari, Shahrokh, and Sifakis, Joseph
- Subjects
- *
ARTIFICIAL neural networks , *INTELLIGENT agents , *INFORMATION retrieval , *BOOLEAN functions , *DATA analysis - Abstract
Neural Networks (NNs) are essential components of intelligent systems because they produce efficient solutions to problems of overwhelming complexity for conventional computing methods. There are lots of papers showing that NNs can approximate a wide variety of functions, but comparatively very few discuss their limitations. To illustrate the role played by information coding in NN computations we define and study sensitive and robust Boolean functions. We also prove that an exponential large set of functions in the first group are exponentially difficult to compute by multiple-layer perceptrons (hence incomputable by single-layer perceptrons) and a comparatively large set of functions in the second one, but not all, are computable by single-layer perceptrons. This suggests that the success of NNs, or lack of it, are in part determined by properties of the learned data sets. Finally we use polynomial threshold perceptrons to compute all Boolean functions with quantum annealing and present in detail a QUBO computation on the D-Wave Advantage. [ABSTRACT FROM AUTHOR]
- Published
- 2021
12. Bi-immunity over 1 Different Size Alphabets.
- Author
-
Calude, Cristian S., Celine, Karen Frilya, Ziyuan Gao, Jain, Sanjay, Staiger, Ludwig, and Stephan, Frank
- Subjects
- *
ALPHABET , *NATURAL numbers , *MARTINGALES (Mathematics) , *UNSOLVABILITY (Mathematical logic) , *RANDOM numbers - Abstract
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 sequence 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. [ABSTRACT FROM AUTHOR]
- Published
- 2021
13. Solomon Marcus Contributions to Theoretical Computer Science and Applications.
- Author
-
Calude, Cristian S. and Păun, Gheorghe
- Subjects
- *
COMPUTER science , *NATURAL computation , *MATHEMATICAL linguistics , *MACHINE theory - Abstract
Solomon Marcus (1925-2016) was one of the founders of the Romanian theoretical computer science. His pioneering contributions to automata and formal language theories, mathematical linguistics and natural computing have been widely recognised internationally. In this paper we briefly present his publications in theoretical computer science and related areas, which consist in almost ninety papers. Finally we present a selection of ten Marcus books in these areas. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
14. A statistical anytime algorithm for the Halting Problem.
- Author
-
Calude, Cristian S. and Dumitrescu, Monica
- Subjects
- *
ALGORITHMS , *ORDER statistics - Abstract
In a previous paper we used computer running times to define a class of computable probability distributions on the set of halting programs and developed a probabilistic anytime algorithm for the Halting Problem. The choice of a computable probability distribution – essential for the algorithm – can be rather subjective and hard to substantiate. In this paper we propose and study an efficient statistical anytime algorithm for the Halting Problem. The main advantage of the statistical algorithm is that it can be implemented without any prior information about the running times on the specific model of computation and the cut-off temporal bound is reasonably small. The algorithm has two parts: the pre-processing which is done only once (when the parameters of the quality of solutions are fixed) and the main part which is run for any input program. With a confidence level as large as required, the algorithm produces correct decisions with a probability as large as required. Three implementations of the algorithm are presented and numerically illustrated. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
15. Searching for shortest and least programs.
- Author
-
Calude, Cristian S., Jain, Sanjay, Merkle, Wolfgang, and Stephan, Frank
- Subjects
- *
COMPUTABLE functions , *DIFFERENCE sets , *RECURSIVE functions , *KOLMOGOROV complexity , *RECURSION theory , *TURING machines - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
16. A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing.
- Author
-
Abbott, Alastair A., Calude, Cristian S., Dinneen, Michael J., and Hua, Richard
- Subjects
- *
QUANTUM annealing , *QUANTUM computers , *GRAPH connectivity , *INDEPENDENT sets , *QUANTUM computing - Abstract
Despite rapid recent progress towards the development of quantum computers capable of providing computational advantages over classical computers, it seems likely that such computers will, initially at least, be required to run in a hybrid quantum-classical regime. This realization has led to interest in hybrid quantum-classical algorithms allowing, for example, quantum computers to solve large problems despite having very limited numbers of qubits. Here we propose a hybrid paradigm for quantum annealers with the goal of mitigating a different limitation of such devices: the need to embed problem instances within the (often highly restricted) connectivity graph of the annealer. This embedding process can be costly to perform and may destroy any computational speedup. In order to solve many practical problems, it is moreover necessary to perform many, often related, such embeddings. We will show how, for such problems, a raw speedup that is negated by the embedding time can nonetheless be exploited to give a real speedup. As a proof-of-concept example we present an in-depth case study of a simple problem based on the maximum-weight independent set problem. Although we do not observe a quantum speedup experimentally, the advantage of the hybrid approach is robustly verified, showing how a potential quantum speedup may be exploited and encouraging further efforts to apply the approach to problems of more practical interest. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
17. Incompleteness and the Halting Problem.
- Author
-
CALUDE, CRISTIAN S.
- Subjects
- *
INCOMPLETENESS theorems , *MATHEMATICAL logic , *SEMANTICS , *COMPUTABLE functions , *INFORMATION theory - Abstract
We present an abstract framework in which we give simple proofs for Gödel's First and Second Incompleteness Theorems and obtain, as consequences, Davis', Chaitin's and Kritchman-Raz's Theorems. [ABSTRACT FROM AUTHOR]
- Published
- 2020
18. Quantum Solutions for Densest K-Subgraph Problems.
- Author
-
Calude, Cristian S., Dinneen, Michael J., and Hua, Richard
- Subjects
- *
SUBGRAPHS , *QUANTUM annealing , *COMPUTATIONAL biology , *INTEGER programming , *QUBITS - Abstract
In this paper we present for the first time quantum annealing solutions for densest K-Subgraph problems which have many applications in computational biology. Our solutions are formulated as solutions for Quadratic Unconstrained Binary Optimisation and Integer Programming problems, proved to be equivalent with the densest K-Subgraph problems and then tested on an D-Wave 2Xmachine. The QUBO formulations are optimal in terms of the number of logical qubits, but require the highest number of physical qubits after embedding. Experimental work reported here suggests that the D-Wave 2XTM model cannot not handle problems of this difficulty. The next generation of D-Wave hardware architecture—the Pegasus architecture—is much denser than the current one, so dense QUBOs will be easier to embed. The experimental work also suggests that the current built-in post-processing optimisation method does not work very well for some problems and the default setting (post-processing optimisation on) should be avoided (or at least tested before being turned on). [ABSTRACT FROM AUTHOR]
- Published
- 2019
19. Liouville, Computable, Borel Normal and Martin-Löf Random Numbers.
- Author
-
Calude, Cristian S. and Staiger, Ludwig
- Subjects
- *
SURVEYS , *REAL numbers , *LIOUVILLE'S theorem , *INTEGERS , *DENSITY - Abstract
We survey the relations between four classes of real numbers: Liouville numbers, computable reals, Borel absolutely-normal numbers and Martin-Löf random reals. Expansions of reals play an important role in our analysis. The paper refers to the original material and does not repeat proofs. A characterisation of Liouville numbers in terms of their expansions will be proved and a connection between the asymptotic complexity of the expansion of a real and its irrationality exponent will be used to show that Martin-Löf random reals have irrationality exponent 2. Finally we discuss the following open problem: are there computable, Borel absolutely-normal, non-Liouville numbers? [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
20. A probabilistic anytime algorithm for the halting problem.
- Author
-
Calude, Cristian S., Dumitrescu, Monica, and Löwe
- Subjects
- *
PROBABILITY theory , *BERNSTEIN polynomials , *ARTIFICIAL intelligence , *MATHEMATICAL programming , *COMPUTER algorithms - Abstract
The Halting Problem, the most (in)famous undecidable problem, has important applications in theoretical and applied computer science and beyond, hence the interest in its approximate solutions. Experimental results reported on various models of computation suggest that halting programs are not uniformly distributed – running times play an important role. A reason is that a program which eventually stops but does not halt “quickly”, stops at a time which is algorithmically compressible. In this paper we work with running times to define a class of computable probability distributions on the set of halting programs in order to construct an anytime algorithm for the Halting problem with a probabilistic evaluation of the error of the decision. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
21. Infinitesimal Probabilities Based on Grossone.
- Author
-
Calude, Cristian S. and Dumitrescu, Monica
- Subjects
- *
PROBABILITY theory , *KOLMOGOROV complexity , *LOGICIANS , *PHYSICISTS , *INTEGERS , *BINOMIAL distribution - Abstract
In finite probability theory the only probability-zero event is the impossible one, but in standard Kolmogorov probability theory probability-zero events occur all the time. Prominent logicians, probability experts and philosophers of probability, including Carnap, Kemeny, Shimony, Savage, De Finetti, Jeffrey, have successfully argued that a sound probability should be regular, that is, only the impossible event should have zero probability. This intuition is shared by physicists too. Totality is another desideratum which means that every event should be assigned a probability. Regularity and totality are achievable in rigorous mathematical terms even for infinite events via hyper-reals valued probabilities. While the mathematics of these theories is not objectionable, some philosophical arguments purport to show that infinitesimal probabilities are inherently problematic. In this paper we present a simpler and natural construction - based on Sergeyev's calculus with Grossone (in a formalism inspired by Lolli) enriched with infinitesimals - of a regular, total, finitely additive, uniformly distributed probability on infinite sets of positive integers. These probability spaces - which are inspired by and parallel the construction of classical probability - will be briefly studied. In this framework De Finetti fair lottery has the natural solution andWilliamson's objections against infinitesimal probabilities are mathematically refuted. Further, in contrast with the classical case, Grossone-like uniform distribution and binomial distribution are infinitely divisible. [ABSTRACT FROM AUTHOR]
- Published
- 2019
22. Finite state incompressible infinite sequences.
- Author
-
Calude, Cristian S., Staiger, Ludwig, and Stephan, Frank
- Subjects
- *
FINITE state machines , *MATHEMATICAL sequences , *INFINITY (Mathematics) , *STRING theory , *MATHEMATICAL mappings - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
23. A Non-Probabilistic Model of Relativised Predictability in Physics.
- Author
-
Abbott, Alastair A., Calude, Cristian S., and Svozil, Karl
- Subjects
- *
LOGICAL prediction , *QUANTUM information theory , *KOCHEN-Specker theorem - Abstract
Unpredictability is an important concept throughout physics and plays a central role in quantum information theory. Despite this, little effort has been devoted to studying generalised notions or models of (un)predictability in physics. In this paper, we continue the programme of developing a general, non-probabilistic model of (un)predictability in physics. We present a more refined model that is capable of studying different degrees of "relativised" unpredictability. This model is based on the ability of an agent, acting via uniform, effective means, to predict correctly and reproducibly the outcome of an experiment using finite information extracted from the environment. We use this model to study the degree of unpredictability certified by different quantum phenomena further, showing that quantum complementarity guarantees a form of relativised unpredictability that is weaker than that guaranteed by Kochen--Specker-type value indefiniteness. We exemplify further the difference between certification by complementarity and value indefiniteness by showing that, unlike value indefiniteness, complementarity is compatible with the production of computable sequences of bits. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
24. A variant of the Kochen-Specker theorem localising value indefiniteness.
- Author
-
Abbott, Alastair A., Calude, Cristian S., and Svozil, Karl
- Subjects
- *
KOCHEN-Specker theorem , *OBSERVABILITY (Control theory) , *QUANTUM mechanics , *SUBSPACES (Mathematics) , *MATHEMATICAL proofs - Abstract
The Kochen-Specker theorem proves the inability to assign, simultaneously, noncontextual definite values to all (of a finite set of) quantum mechanical observables in a consistent manner. If one assumes that any definite values behave noncontextually, one can nonetheless only conclude that some observables (in this set) are value indefinite. In this paper, we prove a variant of the Kochen-Specker theorem showing that, under the same assumption of noncontextuality, if a single one-dimensional projection observable is assigned the definite value 1, then no one-dimensional projection observable that is incompatible (i.e., non-commuting) with this one can be assigned consistently a definite value. Unlike standard proofs of the Kochen- Specker theorem, in order to localise and show the extent of value indefiniteness, this result requires a constructive method of reduction between Kochen-Specker sets. If a system is prepared in a pure state |, then it is reasonable to assume that any value assignment (i.e., hidden variable model) for this system assigns the value 1 to the observable projecting onto the one-dimensional linear subspace spanned by |, and the value 0 to those projecting onto linear subspaces orthogonal to it. Our result can be interpreted, under this assumption, as showing that the outcome of a measurement of any other incompatible one-dimensional projection observable cannot be determined in advance, thus formalising a notion of quantum randomness. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
25. Universality and Almost Decidability.
- Author
-
Calude, Cristian S. and Desfontaines, Damien
- Subjects
- *
DECIDABILITY (Mathematical logic) , *UNARY algebras , *COMPUTATIONAL complexity , *SET theory , *PROBLEM solving , *MATHEMATICAL functions - Abstract
We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result-namely, the existence of infinitely many universal functions whose halting sets are generic (negligible) and not almost decidable-solves an open problem in [9]. We conclude with some open problems. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
26. Preface.
- Author
-
Calude, Cristian S. and Gheorghe, Marian
- Subjects
- *
SPECIAL issues of periodicals , *COMPUTER science research , *MATHEMATICIANS , *COMPUTATIONAL complexity , *MACHINE theory , *COMPUTER programming - Published
- 2014
- Full Text
- View/download PDF
27. INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM.
- Author
-
CALUDE, CRISTIAN S., CALUDE, ELENA, and QUEEN, MELISSA S.
- Subjects
- *
INDUCTIVE logic programming , *COMPUTATIONAL complexity , *PROBLEM solving , *ORDERED sets , *RIEMANN hypothesis - Abstract
This paper does not propose a solution, not even a new possible attack, to the P versus NP problem. We are asking the simpler question: How 'complex' is the P versus NP problem? Using the inductive complexity measure-a measure based on computations run by inductive register machines of various orders-developed in [2], we determine an upper bound on the inductive complexity of second order of the P versus NP problem. From this point of view, the P versus NP problem is significantly more complex than the Riemann hypothesis. To date, the P versus NP problem and the Goostein theorem (which is unprovable in Peano Arithmetic) are the most complex mathematical statements (theorems, conjectures and problems) studied in this framework [9, 5, 6, 2, 20]. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
28. The complexity of Euler’s integer partition theorem
- Author
-
Calude, Cristian S., Calude, Elena, and Queen, Melissa S.
- Subjects
- *
INTEGERS , *EULER theorem , *NUMBER theory , *ALGORITHMS , *APPLIED mathematics , *MATHEMATICAL analysis , *COMPUTATIONAL complexity - Abstract
Abstract: 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) . In this paper, we use the algorithmic method to evaluate the complexity of mathematical statements developed in Calude et al. (2006) and Calude and Calude (2009, 2010) and to show that Euler’s theorem is in class , the same complexity class as the Riemann hypothesis. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
29. Is there a universal image generator?
- Author
-
Calude, Cristian S. and Lewis, J.P.
- Subjects
- *
COMPUTATIONAL complexity , *ALGORITHMS , *DIGITAL image processing , *PATTERN generators , *PATTERN perception , *MATHEMATICAL analysis - Abstract
Abstract: Synthetic pattern generation procedures have various applications, and a number of approaches (fractals, L-systems, etc.) have been devised. A fundamental underlying question is: will new pattern generation algorithms continue to be invented, or is there some “universal” algorithm that can generate all (and only) the perceptually distinguishable images, or even all members of a restricted class of patterns such as logos or letterforms? In fact there are many complete algorithms that can generate all possible images, but most images are random and not perceptually distinguishable. Counting arguments show that the percentage of distinguishable images that will be generated by such complete algorithms is vanishingly small. In this paper we observe that perceptually distinguishable images are compressible. Using this observation it is evident that algorithmic complexity provides an appropriate framework for discussing the question of a universal image generator. We propose a natural thesis for describing perceptually distinguishable images and argue its validity. Based on it, we show that there is no program that generates all (and only) these images. Although this is an abstract result, it may have importance for graphics and other fields that deal with compressible signals. In essence, new representations and pattern generation algorithms will continue to be developed; there is no feasible “super algorithm” that is capable of all things. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
30. Finite state complexity
- Author
-
Calude, Cristian S., Salomaa, Kai, and Roblot, Tania K.
- Subjects
- *
TURING machines , *TRANSDUCERS , *MATHEMATICAL analysis , *COMPUTATIONAL complexity , *COMPUTER algorithms , *INFORMATION theory in mathematics , *MACHINE theory - Abstract
Abstract: 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. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
31. A Multi-Criteria Metric Algorithm for Recommender Systems.
- Author
-
Akhtarzada, Ali, Calude, Cristian S., and Hosking, John
- Abstract
Information overload and an abundance of choices create situations where selecting one option becomes extremely difficult or even worse, a guessing game. Collaborative ranking systems are widely used to alleviate this problem by creating intelligent rankings of items based on an aggregation of user opinions. Current ranking systems can still be improved in a number of areas, including accuracy, transparency and flexibility. This paper presents a multi-criteria ranking algorithm that can be used on a non-rigid set of criteria. The system implementing the algorithm fares well with respect to the above qualities. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
32. Representation of left-computable ε-random reals
- Author
-
Calude, Cristian S., Hay, Nicholas J., and Stephan, Frank
- Subjects
- *
COMPUTABLE functions , *INTEGRAL representations , *PROBABILITY theory , *REAL numbers , *ARITHMETIC , *COMPUTATIONAL mathematics , *TURING machines - Abstract
Abstract: In this paper we introduce the notion of ε-universal prefix-free Turing machine (ε is a computable real in ) and study its halting probability. The main result is the extension of the representability theorem for left-computable random reals to the case of ε-random reals: a real is left-computable ε-random iff it is the halting probability of an ε-universal prefix-free Turing machine. We also show that left-computable ε-random reals are provable ε-random in the Peano Arithmetic. The theory developed here parallels to a large extent the classical theory, but not completely. For example, random reals are Borel normal (in any base), but for , some ε-random reals do not contain even arbitrarily long runs of 0s. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
33. Universal recursively enumerable sets of strings
- Author
-
Calude, Cristian S., Nies, André, Staiger, Ludwig, and Stephan, Frank
- Subjects
- *
INFORMATION theory , *RECURSIVELY enumerable sets , *PROBABILITY theory , *SET theory , *MATHEMATICAL mappings , *UNIVERSAL weight training equipment , *COMPUTER science - Abstract
Abstract: 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 is the domain of a universal plain machine in terms of the description complexity of the spectrum function mapping each non-negative integer to the number of all strings of length in ; 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 of an r.e. prefix-free set containing the domain of a universal prefix-free machine is Martin-Löf random, while 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. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
34. Simplicity via provability for universal prefix-free Turing machines
- Author
-
Calude, Cristian S.
- Subjects
- *
COMPUTATIONAL complexity , *PROBABILITY theory , *TURING machines , *SIGNS & symbols , *FORMAL languages , *SET theory , *COMPUTATIONAL mathematics - Abstract
Abstract: 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. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
35. The complexity of proving chaoticity and the Church-Turing thesis.
- Author
-
Calude, Cristian S., Calude, Elena, and Svozil, Karl
- Subjects
- *
CHAOS theory , *DIFFERENTIABLE dynamical systems , *PROBLEM solving , *MATHEMATICAL proofs , *EMBEDDINGS (Mathematics) , *HAMILTONIAN systems , *COMPUTATIONAL complexity - Abstract
Proving the chaoticity of some dynamical systems is equivalent to solving the hardest problems in mathematics. Conversely, classical physical systems may 'compute the hard or even the incomputable' by measuring observables which correspond to computationally hard or even incomputable problems. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
36. Algorithmically independent sequences
- Author
-
Calude, Cristian S. and Zimand, Marius
- Subjects
- *
ALGORITHMS , *INDEPENDENCE (Mathematics) , *MATHEMATICAL sequences , *INFORMATION theory , *STOCHASTIC processes , *HAUSDORFF measures , *COMPUTATIONAL complexity - Abstract
Abstract: 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. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
37. Topology on words
- Author
-
Calude, Cristian S., Jürgensen, Helmut, and Staiger, Ludwig
- Subjects
- *
TOPOLOGY , *VOCABULARY , *FORMAL languages , *ALPHABETS , *COMBINATION (Linguistics) , *COMPUTER science - Abstract
Abstract: 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. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
38. Most programs stop quickly or never halt
- Author
-
Calude, Cristian S. and Stay, Michael A.
- Subjects
- *
DISTRIBUTION (Probability theory) , *PROBABILITY theory , *CHARACTERISTIC functions , *ROBUST statistics - Abstract
Abstract: The 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 , 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 . 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 has effectively zero density. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
39. Preface
- Author
-
Burgin, Mark and Calude, Cristian S.
- Published
- 2007
- Full Text
- View/download PDF
40. From Heisenberg to Gödel via Chaitin.
- Author
-
Calude, Cristian S. and Stay, Michael A.
- Subjects
- *
HEISENBERG uncertainty principle - Abstract
In 1927 Heisenberg discovered that the “more precisely the position is determined, the less precisely the momentum is known in this instant, and vice versa.” Four years later Gödel showed that a finitely specified, consistent formal system which is large enough to include arithmetic is incomplete. As both results express some kind of impossibility it is natural to ask whether there is any relation between them, and, indeed, this question has been repeatedly asked for a long time. The main interest seems to have been in possible implications of incompleteness to physics. In this note we will take interest in the converse implication and will offer a positive answer to the question: Does uncertainty imply incompleteness? We will show that algorithmic randomness is equivalent to a “formal uncertainty principle” which implies Chaitin’s information-theoretic incompleteness. We also show that the derived uncertainty relation, for many computers, is physical. In fact, the formal uncertainty principle applies to all systems governed by the wave equation, not just quantum waves. This fact supports the conjecture that uncertainty implies algorithmic randomness not only in mathematics, but also in physics. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
41. DE-QUANTIZING THE SOLUTION OF DEUTSCH'S PROBLEM.
- Author
-
CALUDE, CRISTIAN S.
- Subjects
- *
QUANTUM theory , *PROBABILITY theory , *ALGORITHMS , *BOOLEAN algebra , *MATHEMATICAL analysis - Abstract
Probably 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-quantized 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. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
42. EXACT APPROXIMATIONS OF OMEGA NUMBERS.
- Author
-
CALUDE, CRISTIAN S. and DINNEEN, MICHAEL J.
- Subjects
- *
TURING machines , *MACHINE theory , *APPROXIMATION theory , *BIFURCATION theory , *DYNAMICS - Abstract
A Chaitin Omega number is the halting probability of a universal prefix-free Turing machine. Every Omega number is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable. The value of an Omega number is highly machine-dependent. In general, no more than finitely many scattered bits of the binary expansion of an Omega number can be exactly computed; but, in some cases, it is possible to prove that no bit can be computed. In this paper, we will simplify and improve both the method and correctness of the proof proposed in an earlier paper, and we will compute the exact approximations of two Omega numbers of the same prefix-free Turing machine, which is universal when used with data in base 16 or base 2: we compute 43 exact bits for the base 16 machine and 40 exact bits for the base 2 machine. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
43. Natural halting probabilities, partial randomness, and zeta functions
- Author
-
Calude, Cristian S. and Stay, Michael A.
- Subjects
- *
TURING machines , *MACHINE theory , *STATISTICAL correlation , *ALGORITHMS - Abstract
Abstract: 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. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
44. Automata Recognizing No Words: A Statistical Approach.
- Author
-
Calude, Cristian S., Câmpeanu, Cezar, and Dumitrescu, Monica
- Subjects
- *
MACHINE theory , *STATISTICS , *PROBABILITY theory , *SEQUENTIAL machine theory - Abstract
How 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. 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 the last section we critically discuss the result and the method used in this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2006
45. On partial randomness
- Author
-
Calude, Cristian S., Staiger, Ludwig, and Terwijn, Sebastiaan A.
- Subjects
- *
MACHINE theory , *STOCHASTIC processes , *PREDICTION theory , *ELECTRONIC data processing - Abstract
Abstract: If is a random sequence, then the sequence is clearly not random; however, seems to be “about half random”. L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 (1993) 159–194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 (1998) 215–229] and K. Tadaki [A generalisation of Chaitin’s halting probability and halting self-similar sets, Hokkaido Math. J. 31 (2002) 219–253] have studied the degree of randomness of sequences or reals by measuring their “degree of compression”. This line of study leads to various definitions of partial randomness. In this paper we explore some relations between these definitions. Among other results we obtain a characterisation of -dimension (as defined by Schnorr and Lutz in terms of martingales) in terms of strong Martin-Löf -tests (a variant of Martin-Löf tests), and we show that -randomness for is different (and more difficult to study) than the classical 1-randomness. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
46. Is complexity a source of incompleteness?
- Author
-
Calude, Cristian S. and Jürgensen, Helmut
- Subjects
- *
PROBABILITY theory , *MATHEMATICAL logic , *OPERATIONS research , *MATHEMATICAL combinations - Abstract
Abstract: In this paper we prove Chaitin''s “heuristic principle,”the theorems of a finitely-specified 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ödel 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. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
47. From Heisenberg to Gödel via Chaitin.
- Author
-
Svozil, Karl, Calude, Cristian S., and Stay, Michael A.
- Subjects
- *
HEISENBERG uncertainty principle , *QUANTUM theory , *PARTIAL differential equations , *MATHEMATICS , *PHYSICS , *MECHANICS (Physics) - Abstract
In 1927, Heisenberg discovered that the “more precisely the position is determined, the less precisely the momentum is known in this instant, and vice versa.” Four years later Gödel showed that a finitely specified, consistent formal system which is large enough to include arithmetic is incomplete. As both results express some kind of impossibility it is natural to ask whether there is any relation between them, and, indeed, this question has been repeatedly asked for a long time. The main interest seems to have been in possible implications of incompleteness to physics. In this note we will take interest in the converse implication and will offer a positive answer to the question: Does uncertainty imply incompleteness? We will show that algorithmic randomness is equivalent to a “formal uncertainty principle” which implies Chaitin's information-theoretic incompleteness. We also show that the derived uncertainty relation, for many computers, is physical. In fact, the formal uncertainty principle applies to all systems governed by the wave equation, not just quantum waves. This fact supports the conjecture that uncertainty implies algorithmic randomness not only in mathematics, but also in physics. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
48. Generalisations of disjunctive sequences.
- Author
-
Calude, Cristian S. and Staiger, Ludwig
- Subjects
- *
MATHEMATICAL sequences , *ALGEBRA , *MATHEMATICS , *BAIRE classes , *REAL variables , *COMPLEX variables - Abstract
The 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. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
49. Proving as a Computable Procedure.
- Author
-
Calude, Cristian S. and Rudeanu, Sergiu
- Subjects
- *
GODEL'S theorem , *INCOMPLETENESS theorems , *HILBERT schemes , *NUMBER theory , *FOUNDATIONS of arithmetic , *MATHEMATICAL logic - Abstract
Gödel's incompleteness theorem states that every finitely-presented, consistent, sound theory which is strong enough to include arithmetic is incomplete. In this paper we present elementary proofs for three axiomatic variants of Gödel's incompleteness theorem and we use them (a) to illustrate the idea that there is more than "complete vs. incomplete" there are degrees of incompleteness, and (b) to discuss the implications of incompleteness and computer-assisted proofs for Hilbert's Programme. We argue that the impossibility of carrying out Hilbert's Programme is a thesis and has a similar status to the Church-Turing thesis. [ABSTRACT FROM AUTHOR]
- Published
- 2005
50. Bio-steps beyond Turing
- Author
-
Calude, Cristian S. and Păun, Gheorghe
- Subjects
- *
TURING test , *BRAIN , *MATHEMATICAL functions , *CREATIVE ability , *LIFE sciences - Abstract
Are there ‘biologically computing agents’ capable to compute Turing uncomputable functions? It is perhaps tempting to dismiss this question with a negative answer. Quite the opposite, for the first time in the literature on molecular computing we contend that the answer is not theoretically negative. Our results will be formulated in the language of membrane computing (P systems). Some mathematical results presented here are interesting in themselves. In contrast with most speed-up methods which are based on non-determinism, our results rest upon some universality results proved for deterministic P systems. These results will be used for building “accelerated P systems”. In contrast with the case of Turing machines, acceleration is a part of the hardware (not a quality of the environment) and it is realised either by decreasing the size of “reactors” or by speeding-up the communication channels. Consequently, two acceleration postulates of biological inspiration are introduced; each of them poses specific questions to biology. Finally, in a more speculative part of the paper, we will deal with Turing non-computability activity of the brain and possible forms of (extraterrestrial) intelligence. [Copyright &y& Elsevier]
- Published
- 2004
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.