Epstein and Carnielli's fine textbook on logic and computability is now in its second edition. The readers of this journal might be particularly interested in the timeline `Computability and Undecidability' added in this edition, and the included wall-poster of the same title. The text itself, however, has some aspects which are worth commenting on.

The aim of this paper is an attempt to give an answer to the question what does it mean that a computational system is intelligent. We base on some theses that though debatable are commonly accepted. Intelligence is conceived as the ability of tractable solving of some problems that in general are not solvable by deterministic Turing Machine.

Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps the (...) developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

This paper starts from the observation that the standard arguments for compositionality are really arguments for the computability of semantics. Since computability does not entail compositionality, the question of what justifies compositionality recurs. The paper then elaborates on the idea of recursive semantics as corresponding to computable semantics. It is then shown by means of time complexity theory and with the use of term rewriting as systems of semantic computation, that syntactically unrestricted, noncompositional recursive semantics leads to computational explosion (factorial (...) complexity). Hence, with combinatorially unrestricted syntax, semantics with tractable time complexity is compositional. (shrink)

This article focuses on the relevance of computational complexity for cognition. The syntactic items may be expressions that are surface strings. But in general, strings are syntactically ambiguous in that they can be generated in more than one way from atomic expressions and operations. The semantic function must take disambiguated items as arguments. When expressions are ambiguous, expressions cannot be the arguments. Instead, it is common to take the arguments to be terms, whose surface syntax reflects the derivation of the (...) string. The semantic function differs in one other important respect from an arithmetic function, since it maps entities between domains, from a syntactic to an ontic or conceptual domain of meanings. Compositionality helps to explain the rate of success in linguistic communication when the sentence used or the content communicated is new. (shrink)

Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm was soon followed by several (...) other algorithms that aimed to solve combinatorial and algebraic problems, and in the years since theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor’s algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premise that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in attempts to tackle the technological difficulties that prevent the realisation of a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995; Ekert and Jozsa 1996; Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. -/- The philosophical interest in quantum computing is manifold. From a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for harnessing the power of 50–100 qubits (the basic unit of information in the quantum computer) is now within reach (Preskill 2018), only a handful of quantum algorithms exist, and the question of whether these can truly outperform any conceivable classical alternative is still open. From a more philosophical perspective, advances in quantum computing may yield foundational benefits. For example, it may turn out that the technological capabilities that allow us to isolate quantum systems by shielding them from the effects of decoherence for a period of time long enough to manipulate them will also allow us to make progress in some fundamental problems in the foundations of quantum theory itself. Indeed, the development and the implementation of efficient quantum algorithms may help us understand better the border between classical and quantum physics (Cuffaro 2017, 2018a; cf. Pitowsky 1994, 100), and perhaps even illuminate fundamental concepts such as measurement and causality. Finally, the idea that abstract mathematical concepts such as computability and complexity may not only be translated into physics, but also re-written by physics bears directly on the autonomous character of computer science and the status of its theoretical entities—the so-called “computational kinds”. As such it is also relevant to the long-standing philosophical debate on the relationship between mathematics and the physical world. (shrink)

In this paper we defend structural representations, more specifically neural structural representation. We are not alone in this, many are currently engaged in this endeavor. The direction we take, however, diverges from the main road, a road paved by the mathematical theory of measure that, in the 1970s, established homomorphism as the way to map empirical domains of things in the world to the codomain of numbers. By adopting the mind as codomain, this mapping became a boon for all those (...) convinced that a representation system should bear similarities with what was being represented, but struggled to find a precise account of what such similarities mean. The euforia was brief, however, and soon homomorphism revealed itself to be affected by serious weaknesses, the primary one being that it included systems embarrassingly alien to representations. We find that the defense attempts that have followed, adopt strategies that share a common format: valid structural representations come as “homomorphism plus X”, with various “X”, provided in descriptive format only. Our alternative direction stems from the observation of the overlooked departure from homomorphism as used in the theory of measure and its later use in mental representations. In the former case, the codomain or the realm of numbers, is the most suited for developing theorems detailing the existence and uniqueness of homomorphism for a wide range of empirical domains. In the latter case, the codomain is the realm of the mind, possibly more vague and more ill-defined than the empirical domain itself. The time is ripe for articulating the mapping between represented domains and the mind in formal terms, by exploiting what is currently known about coding mechanisms in the brain. We provide a sketch of a possible development in this direction, one that adopts the theory of neural population coding as codomain. We will show that our framework is not only not in disagreement with the “plus X” proposals, but can lead to natural derivation of several of the “X”. (shrink)

In this paper we defend structural representations, more specifically neural structural representation. We are not alone in this, many are currently engaged in this endeavor. The direction we take, however, diverges from the main road, a road paved by the mathematical theory of measure that, in the 1970s, established homomorphism as the way to map empirical domains of things in the world to the codomain of numbers. By adopting the mind as codomain, this mapping became a boon for all those (...) convinced that a representation system should bear similarities with what was being represented, but struggled to find a precise account of what such similarities mean. The euforia was brief, however, and soon homomorphism revealed itself to be affected by serious weaknesses, the primary one being that it included systems embarrassingly alien to representations. We find that the defense attempts that have followed, adopt strategies that share a common format: valid structural representations come as “homomorphism plus X”, with various “X”, provided in descriptive format only. Our alternative direction stems from the observation of the overlooked departure from homomorphism as used in the theory of measure and its later use in mental representations. In the former case, the codomain or the realm of numbers, is the most suited for developing theorems detailing the existence and uniqueness of homomorphism for a wide range of empirical domains. In the latter case, the codomain is the realm of the mind, possibly more vague and more ill-defined than the empirical domain itself. The time is ripe for articulating the mapping between represented domains and the mind in formal terms, by exploiting what is currently known about coding mechanisms in the brain. We provide a sketch of a possible development in this direction, one that adopts the theory of neural population coding as codomain. We will show that our framework is not only not in disagreement with the “plus X” proposals, but can lead to natural derivation of several of the “X”. (shrink)

This paper investigates some delicate tradeoffs between the generality of an algorithmic learning device and the quality of the programs it learns successfully. There are results to the effect that, thanks to small increases in generality of a learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. There are also results in which the complexity of successfully learned programs is asymptotically optimal and the learning device is general, but, still thanks to the generality, some of (...) those optimal, learned programs are provably unalterably information deficient—in some cases, deficient as to safe, algorithmic extractability/provability of the fact that they are even approximately optimal. For these results, the safe, algorithmic methods of information extraction will be by proofs in arbitrary, true, computably axiomatizable extensions of Peano Arithmetic. (shrink)

In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial time representation of a countably infinite dimensional vector space V∞ over a finite field F. We show that for both the standard and tally representation of V∞, there exists polynomial time subspaces U and W such that U + V is not recursive. We also study the NP analogues of simple and maximal subspaces. We show that the existence of (...) P-simple and NP-maximal subspaces is oracle dependent in both the tally and standard representations of V∞. This contrasts with the case of sets, where the existence of NP-simple sets is oracle dependent but NP-maximal sets do not exist. We also extend many results of Nerode and Remmel concerning the relationship of P bases and NP-subspaces in the tally representation of V∞ to the standard representation of V∞. (shrink)

The often observed complexity gap between the expressiveness of a logical formalism and its exponentially harder expression complexity is proven for all logical formalisms which satisfy natural closure conditions. The expression complexity of the prefix classes of second-order logic can thus be located in the corresponding classes of the weak exponential hierarchies; further results about expression complexity in database theory, logic programming, nonmonotonic reasoning, first-order logic with Henkin quantifiers and default logic are concluded. The proof method illustrates the significance of (...) quantifier-free interpretations in descriptive complexity theory. (shrink)

The spectrum of a first-order sentence is the set of natural numbers occurring as the cardinalities of finite models of the sentence. In a recent survey, Durand et al. introduce a new class of real numbers, the spectral reals, induced by spectra and pose two open problems associated to this class. In the present note, we answer these open problems as well as other open problems from an earlier, unpublished version of the survey. Specifically, we prove that every algebraic real (...) is spectral, every automatic real is spectral, the subword density of a spectral real is either 0 or 1, and both may occur, and every right-computable real number between 0 and 1 occurs as the subword entropy of a spectral real. In addition, Durand et al. note that the set of spectral reals is not closed under addition or multiplication. We extend this result by showing that the class of spectral reals is not closed under any computable operation satisfying some mild conditions. (shrink)

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...) never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact. (shrink)