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.

It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct values (a.k.a. colors or priorities)---is proven to be in the class of fixed parameter tractable problems when parameterized over $m$. Both results improve known bounds, from runtime $n^{O(\sqrt{n})}$ to $O(n^{\log(m)+6})$ and from an XP algorithm with runtime $O(n^{\Theta(m)})$ for fixed parameter $m$ to a fixed parameter tractable algorithm with runtime $O(n^5+2^{m\log(m)+6m})$. As an application, it is proven that colored Muller games with $n$ nodes and $m$ colors can be decided in time $O((m^m \cdot n)^5)$; it is also shown that this bound cannot be improved to $2^{o(m \cdot \log(m))} \cdot n^{O(1)}$ in the case that the exponential time hypothesis is true. Further investigations deal with memoryless Muller games and multidimensional parity games.

It is shown that the parity game can be solved in quasipolynomial time. The parameterised parity game - with n nodes and m distinct values (aka colours or priorities) - is proven to be in the class of fixed parameter tractable (FPT) problems when parameterised over m. Both results improve known bounds, from runtime nO(√n) to O(nlog(m)+6) and from an XP-algorithm with runtime O(nΘ(m)) for fixed parameter m to an FPT-algorithm with runtime O(n5)+g(m), for some function g depending on m only. As an application it is proven that coloured Muller games with n nodes and m colours can be decided in time O((mm · n)5); it is also shown that this bound cannot be improved to O((2m · n)c), for any c, unless FPT = W[1].

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.

The mathematician and logician Gr. C. Moisil (1906-1973) played a fundamental role in the introduction and the development of computer science in Romania and in raising the first generations of

In this paper we propose a quantum random number generator (QRNG) that uses an entangled photon pair in a Bell singlet state and is certified explicitly by value indefiniteness. While ‘true randomness’ is a mathematical impossibility, the certification by value indefiniteness ensures that the quantum random bits are incomputable in the strongest sense. This is the first QRNG setup in which a physical principle (Kochen–Specker value indefiniteness) guarantees that no single quantum bit that is produced can be classically computed (reproduced and validated), which is the mathematical form of bitwise physical unpredictability. We discuss the effects of various experimental imperfections in detail: in particular, those related to detector efficiencies, context alignment and temporal correlations between bits. The analysis is very relevant for the construction of any QRNG based on beam-splitters. By measuring the two entangled photons in maximally misaligned contexts and using the fact that two bitstrings, rather than just one, are obtained, more efficient and robust unbiasing techniques can be applied. We propose a robust and efficient procedure based onXORing the bitstrings together – essentially using one as a one-time-pad for the other – to extract random bits in the presence of experimental imperfections, as well as a more efficient modification of the von Neumann procedure for the same task. We also discuss some open problems.

Albert Einstein encapsulated a commonly held view within the scientific community when he wrote in his book Out of My Later Years (Einstein 1950, page 54) ‘When we say that we understand a group of natural phenomena, we mean that we have found a constructive theory which embraces them.’ This represents a dual challenge to the scientist: on the one hand, to explain the real world in a very basic, and if possible, mathematical, way; but on the other, to characterise the extent to which this is even possible. Recent years have seen the mathematics of computability play an increasingly vital role in pushing forward basic science and in illuminating its limitations within a creative coming together of researchers from different disciplines. This special issue of Mathematical Structures in Computer Science is based on the special session ‘Computability of the Physical’ at the International Conference Computability in Europe 2010, held at Ponta Delgada, Portugal, in June 2010, and it, together with the individual papers it contains, forms what we believe to be a special contribution to this exciting and developing process.

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.

In this paper we prove that any Turing machine that uses only a finite computational space for every input cannot solve an uncomputable problem even when it runs in accelerated mode. We also propose two ways to define the language accepted by an accelerated Turing machine. Accordingly, the classes of languages accepted by accelerated Turing machines are the closure under Boolean operations of the sets Σ1 and Σ2.

We study computably enumerable (c.e.) prefix codes that 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 if and only if 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.

The minimization of nondeterministic automata without initial states (developed \nwithin a game-theoretic framework in Calude, Calude, Khoussainov [3]) is presented \nin terms of bisimulations; the minimal automaton is unique up to an isomorphism \nin case of reversible automata. We also prove that there exists an in nite class \nof (strongly connected) nondeterministic automata each of which is not bisimilar \nwith any deterministic automaton. This shows that in the sense of bisimilarity \nnondeterministic automata are more powerful than deterministic ones. It is an open \nquestion whether the method of bisimulations can produced, in general, the unique \nminimal nondeterministic automaton.

How fast can one approximate a real by a computable sequence of rationals? Rather surprisingly, we show that the answer to this question depends very much on the information content in the finite prefixes of the binary expansion of the real. Computable reals, whose binary expansions have a very low information content, can be approximated (very fast) with a computable convergence rate. Random reals, whose binary expansions contain very much information in their prefixes, can be approximated only very slowly by computable sequences of rationals (this is the case, for example, for Chaitin's Ω numbers) if they can be computably approximated at all. We also show that one can computably approximate any computable real very slowly, with a convergence rate slower than any computable function. However, there is still a large gap between computable reals and random reals: any computable sequence of rationals which converges (monotonically) to a random real converges slower than any computable sequence of rationals which converges (monotonically) to a computable real.