We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 and the (...) class of Sep-computable multivalued functions. Extending work of Brattka, we show that a natural multivalued function associated with the Hahn-Banach Extension Theorem is Sep-complete. (shrink)

This Article takes the perspective of law and philosophy, integrating insights from computer science. First, I will argue that in the era of big data analytics we need an understanding of privacy that is capable of protecting what is uncountable, incalculable or incomputable about individual persons. To instigate this new dimension of the right to privacy, I expand previous work on the relational nature of privacy, and the productive indeterminacy of human identity it implies, into an ecological understanding of (...) privacy, taking into account the technological environment that mediates the constitution of human identity. Second, I will investigate how machine learning actually works, detecting a series of design choices that inform the accuracy of the outcome, each entailing trade-offs that determine the relevance, validity and reliability of the algorithm’s accuracy for real life problems. I argue that incomputability does not call for a rejection of machine learning per se but calls for a research design that enables those who will be affected by the algorithms to become involved and to learn how machines learn — resulting in a better understanding of their potential and limitations. A better understanding of the limitations that are inherent in machine learning will deflate some of the eschatological expectations, and provide for better decision-making about whether and if so how to implement machine learning in specific domains or contexts. I will highlight how a reliable research design aligns with purpose limitation as core to its methodological integrity. This Article, then, advocates a practice of “agonistic machine learning” that will contribute to responsible decisions about the integration of data-driven applications into our environments while simultaneously bringing them under the Rule of Law. This should also provide the best means to achieve effective protection against overdetermination of individuals by machine inferences. (shrink)

In light of the structural role of computational technology in the expansion of modern global finance, this essay investigates the ontology of contemporary markets starting from a reformulation of liquidity—one of the tenets of financial trading. Focusing on the nexus between financial and algorithmic flows, the paper complements contemporary philosophies of the market with insights into recent theories of computation, emphasizing the functional role of contingency, both for market trading and algorithmic processes. Considering the increasing adoption of advanced computational methods (...) in automated trading strategies, this article argues that the event of price is the direct manifestation of the incomputability at the heart of market exchange. In doing so, it questions the ontological assumptions of “flow” and “fluidity” underpinning traditional conceptions of liquidity and challenges the notion of rationality in market behavior. Ultimately, the paper gestures toward some of the social and political consequences of this reformulation. (shrink)

La cognition algorithmique joue un rôle central dans le capitalisme contemporain. Depuis la rationalisation du travail industriel et des relations sociales jusqu’à la finance, les algorithmes fondent un nouveau mode de pensée et de contrôle. Dans cette phase du tout-machinique dans l’évolution du capitalisme numérique, il ne suffit plus de se mettre du côté de la théorie critique pour accuser la computation de réduire la pensée humaine à des opérations mécaniques. Comme le théoricien de l’information Gregory Chaitin l’a démontré ; (...) l’incomputabilité et l’aléatoire doivent être conçus comme les conditions de bases de la computation. Si le technocapitalisme est contaminé par l’aléatoire computationnel et le chaos, la critique traditionnelle de la rationalité instrumentale doit elle aussi être remise en question : l’incomputable ne pleut plus être réduit au statut de contraire de la raison. (shrink)

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

We use Demuth randomness to study strong lowness properties of computably enumerable sets, and sometimes of Δ20 sets. A set A⊆N is called a base for Demuth randomness if some set Y Turing above A is Demuth random relative to A. We show that there is an incomputable, computably enumerable base for Demuth randomness, and that each base for Demuth randomness is strongly jump-traceable. We obtain new proofs that each computably enumerable set below all superlow Martin-Löf random sets is (...) strongly jump traceable, using Demuth tests. The sets Turing below each ω2-computably approximable Martin-Löf random set form a proper subclass of the bases for Demuth randomness, and hence of the strongly jump traceable sets. The c.e. sets Turing below each ω2-computably approximable Martin-Löf random set satisfy a new, very strong combinatorial lowness property called ω-traceability. (shrink)

We expand our effective framework for weak convergence of measures on the real line by showing that effective convergence in the Prokhorov metric is equivalent to effective weak convergence. In addition, we establish a framework for the study of the effective theory of vague convergence of measures. We introduce a uniform notion and a non-uniform notion of vague convergence, and we show that both these notions are equivalent. However, limits under effective vague convergence may not be computable even when they (...) are finite. We give an example of a finite incomputable effective vague limit measure, and we provide a necessary and sufficient condition so that effective vague convergence produces a computable limit. Finally, we determine a sufficient condition for which effective weak and vague convergence of measures coincide. As a corollary, we obtain an effective version of the equivalence between classical weak and vague convergence of sequences of probability measures. (shrink)

Nick Bostrom’s recently patched ‘‘simulation argument’’ (Bostrom in Philos Q 53:243–255, 2003; Bos- trom and Kulczycki in Analysis 71:54–61, 2011) purports to demonstrate the probability that we ‘‘live’’ now in an ‘‘ancestor simulation’’—that is as a simulation of a period prior to that in which a civilization more advanced than our own—‘‘post-human’’—becomes able to simulate such a state of affairs as ours. As such simulations under consid- eration resemble ‘‘brains in vats’’ (BIVs) and may appear open to similar objections, the (...) paper begins by reviewing objections to BIV-type proposals, specifically those due a presumed mad envatter. In counter example, we explore the motivating rationale behind current work in the development of psychologically realistic social simula- tions. Further concerns about rendering human cognition in a computational medium are confronted through review of current dynamic systems models of cognitive agency. In these models, aspects of the human condition are repro- duced that may in other forms be considered incomputable, i.e., political voice, predictive planning, and consciousness. The paper then argues that simulations afford a unique potential to secure a post-human future, and may be nec- essary for a pre-post-human civilization like our own to achieve and to maintain a post-human situation. Long-s- tanding philosophical interest in tools of this nature for Aristotle’s ‘‘statesman’’ and more recently for E.O. Wilson in the 1990s is observed. Self-extinction-level threats from State and individual levels of organization are compared, and a likely dependence on large-scale psychologically realistic simulations to get past self-extinction-level threats is projected. In the end, Bostrom’s basic argument for the conviction that we exist now in a simulation is reaffirmed. (shrink)

We show that the _sQ_-degree of a hypersimple set includes an infinite collection of \(sQ_1\) -degrees linearly ordered under \(\le _{sQ_1}\) with order type of the integers and each c.e. set in these _sQ_-degrees is a hypersimple set. Also, we prove that there exist two c.e. sets having no least upper bound on the \(sQ_1\) -reducibility ordering. We show that the c.e. \(sQ_1\) -degrees are not dense and if _a_ is a c.e. \(sQ_1\) -degree such that \(o_{sQ_1}, then there exist (...) infinitely many pairwise _sQ_-incomputable c.e. _sQ_-degrees \(\{c_i\}_{i\in \omega }\) such that \((\forall \,i)\;(a. (shrink)

Aesthetic investigations of computation are stuck in an impasse, caused by the difficulty of accounting for the ontological discrepancy between the continuity of sensation and the discreteness of digital technology. This article proposes a theoretical position intended to overcome that deadlock. It highlights how an ontological focus on continuity has entered media studies via readings of Deleuze, which attempt to build a ‘digital aisthesis’ by ascribing a ‘virtuality’ to computation. This underpins, in part, the affective turn in digital theory. In (...) contrast to such positions, this article argues for a reconceptualization of formal abstraction in computation, in order to find, within the discreteness of computational formalisms, an indeterminacy that would make computing aesthetic qua inherently generative. This indeterminacy, it is argued here, can be found by reconsidering, philosophically, Turing’s notion of ‘incomputability’. (shrink)

We claim that a recent article of P. Cotogno ([2003]) in this journal is based on an incorrect argument concerning the non-computability of diagonal functions. The point is that whilst diagonal functions are not computable by any function of the class over which they diagonalise, there is no ?logical incomputability? in their being computed over a wider class. Hence this ?logical incomputability? regrettably cannot be used in his argument that no hypercomputation can compute the Halting problem. This seems to lead (...) him into a further error in his analysis of the supposed conventional status of the infinite time Turing machines of Hamkins and Lewis ([2000]). Theorem 1 refutes this directly. The diagonalisation misunderstanding Infinite computation Conclusion. (shrink)

Referring to MacOS’s »swoosh« as the signal of a successfully sent E-Mail the paper looks into the contribution of cultural values to communication with invisible machines. This contribution can be assessed within the context of Talcott Parsons’ action theory which addresses culture as one of four functional aspects of any one action (L), the other three being adaptation to physical, material, and technical environment (A), reference to the goal-attainment of both organism and personality (G), and the integration into, and differentiation (...) from, other action (I). The swoosh signals an »infrathin«, i.e. fleeting, connection of black boxes like machine, body, consciousness, and society being interrelated orthogonally. A culture develops, which momentarily leaves open the question whether or what controls whom or what, even though the calculi of computation themselves are becoming ever more incomputable. (shrink)

The focus of this paper is the incomputability of some topological functions using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ℝn, like closure, border, intersection, and derivative, and we prove for such functions results of Σ02-completeness and Σ03-completeness in the effective Borel hierarchy. Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and Urysohn-Tietze for generic metric spaces (...) . Both lemmas define Σ02-computable functions which in some cases are even Σ02-complete. (shrink)

It is argued that the truth status of emergent properties of complex adaptive systems models should be based on an epistemology of proof by constructive verification and therefore on the ontological axioms of a non-realist logical system such as constructivism or intuitionism. ‘Emergent’ properties of complex adaptive systems models create particular epistemological and ontological challenges. These challenges bear directly on current debates in the philosophy of mathematics and in theoretical computer science. CAS research, with its emphasis on computer simulation, is (...) heavily reliant on models which explore the entailments of Formal Axiomatic Systems. The incompleteness results of G¨odel, the incomputability results of Turing, and the Algorithmic Information Theory results of Chaitin, undermine a realist truth model of emergent properties. These same findings support the hegemony of epistemology over ontology and point to alternative truth models such as intuitionism, constructivism and quasi-empiricism. (shrink)

Initially coined by Weizenbaum in 1976, ‘alien' thought refers to the radical difference with which ‘thinking machines’ approach the process of thinking. The contemporary paradox of over-determination and indeterminacy—caused largely by algorithmic decision-making in the civic realm—makes these differences both more entangled and more difficult to navigate. In this essay, I trace over-determination to Leibniz and Turing’s axiomatic procedures and to instrumental rationality, and I trace indeterminacy to the mid-twentieth century co-development of computers and neurosciences to advance the following proposition: (...) understanding alien thought requires understanding incomputability, temporal swarming, and inscriptive-significational errance. Understanding these phenomena in turn requires understanding thinking by doing, distributed thinking, and ontological indeterminacy. All are present in machinic operations as well as in the twentieth century experimental artistic practices of artists such as Duchamp, Cage, and Xu. These practices rely on indeterminate procedures and function as diagrammatic machines. A diagrammatic machine is neither abstract nor particular; neither an idea that is determining in the supreme instance, nor an infrastructure that is determining in the last instance, but rather instantiates a real yet to come (Deleuze and Guattari in A thousand plateaus: capitalism and schizophrenia: Trans. Massumi B, University of Minnesota Press, Minneapolis, 1987). In this essay, indeterminate artistic practices are used as an entry into alien thought and its correlates—infinity and complexity—by way of aesthetic analogy. (shrink)

We investigate in the frame of TTE the computability of functions of the measurable sets from an infinite computable measure space such as the measure and the four kinds of set operations. We first present a series of undecidability and incomputability results about measurable sets. Then we construct several examples of computable topological spaces from the abstract infinite computable measure space, and analyze the computability of the considered functions via respectively each of the standard representations of the computable topological spaces (...) constructed. (shrink)

The article reports the results from the developmentof four data-driven discovery systems, operating inlinguistics. The first mimics the induction methods ofJohn Stuart Mill, the second performs componentialanalysis of kinship vocabularies, the third is ageneral multi-class discrimination program, and thefourth finds logical patterns in data. These systemsare briefly described and some arguments are offeredin favour of machine linguistic discovery. Thearguments refer to the strength of machines incomputationally complex tasks, the guaranteedconsistency of machine results, the portability ofmachine methods to new tasks and (...) domains, and thepotential machines provide for our gaining newinsights. (shrink)

This article takes inspiration from Kittler’s claim that philosophy has neglected the means used for its production. Kittler’s argument for media ontology will be compared to the post-Kantian project of re-inventing philosophy through the medium of thought. The article discusses these views in the context of the automation of logical thinking where procedures, tasks, and functions are part of the instrumental processing of new ends evolving a new mode of reasoning. In particular, the article suggests that in constructivist logic and (...) information theory, the temporal gap between truth and proof, between input and output, can be taken to argue that the means of thought expose the indetermination or the incomputability of proof. The automation of reasoning in logical processing coincides not with mindless correlations of data, replacing axioms with data, truths with self-validating proofs. Instead, the problem of the indeterminacy of proof within automated logic re-habilitates techne or instrumentality, and the relation between means and ends away from classical idealism and analytic realism. By following John Dewey’s argument for instrumentality, it will be argued that the task of thinking today needs to re-invent a logic of techne away from the teleological view of ends or the crisis of finality. If the post-Kantian preoccupations about the task of thinking already announced that the medium of thought could offer possibilities for a non-human philosophy, this article envisions a machine philosophy originating from within computational media. (shrink)

This article tackles an old, classical problem, which is acquiring a new epochal relevance with the techno-aesthetic processing of form and substance, expression and content. The field of digital architecture is embarked in the ancient controversy between the line and the curve, binary communication and fuzzy logic. Since the 1990s, the speculative qualities of digital architecture have exposed spatial design to the qualities of growing or breeding, rather than planning. However, such qualities still deploy the tension between discrete spaces and (...) continual curving. In this context, the article suggests the computational coexistence of discrete coding with continual morphing, defying any easy resolution for an aesthetic of continuity or discontinuity, the superiority of the analog or the meta-logic of the digital. The metaphysical dimension of such coexistence needs to include the abstract capacities of experiencing the transition from one state to another as the registering of algorithmic processing. Computation is intrinsic to microperceptions, incomputable quantities deploying the infectious property of the digital code. The article draws on the digital architecture of Greg Lynn to explore whether the computational nature of the digital calculus has the potential to challenge the bifurcation between the biological and the mathematical, the physical and the mental. (shrink)

Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinite-time oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for non-terminating processes are (...) likewise irrelevant, since diagonalization can cover any amount of value assignments. This should not be construed as a restriction of computing power: Turing’s uncomputability is not a ‘barrier’ to be broken, but simply an effect of the expressive power of consistent programming systems. (shrink)

This special issue introduces the study of financial technologies and finance to the field of philosophy of technology, bringing together two different fields that have not traditionally been in dialogue. The included articles are: Digital Art as ‘Monetised Graphics’: Enforcing Intellectual Property on the Blockchain, by Martin Zeilinger; Fundamentals of Algorithmic Markets: Liquidity, Contingency, and the Incomputability of Exchange, by Laura Lotti; ‘Crises of Modernity’ Discourses and the Rise of Financial Technologies in a Contested Mechanized World, by Marinus Ossewaarde; Two (...) Technical Images: Blockchain and High-Frequency Trading, by Diego Viana; and The Blockchain as a Narrative Technology: Investigating the Social Ontology and Normative Configurations of Cryptocurrencies, by Wessel Reijers and Mark Coeckelbergh. (shrink)

This special issue introduces the study of financial technologies and finance to the field of philosophy of technology, bringing together two different fields that have not traditionally been in dialogue. The included articles are: Digital Art as ‘Monetised Graphics’: Enforcing Intellectual Property on the Blockchain, by Martin Zeilinger; Fundamentals of Algorithmic Markets: Liquidity, Contingency, and the Incomputability of Exchange, by Laura Lotti; ‘Crises of Modernity’ Discourses and the Rise of Financial Technologies in a Contested Mechanized World, by Marinus Ossewaarde; Two (...) Technical Images: Blockchain and High-Frequency Trading, by Diego Viana; and The Blockchain as a Narrative Technology: Investigating the Social Ontology and Normative Configurations of Cryptocurrencies, by Wessel Reijers and Mark Coeckelbergh. (shrink)

We prove that if is an ω-model of weak weak König’s lemma and , is incomputable, then there exists , such that A and B are Turing incomparable. This extends a recent result of Kučera and Slaman who proved that if is a Scott set and , Aω, is incomputable, then there exists , Bω, such that A and B are Turing incomparable.

Alan Turing anticipated many areas of current research incomputer and cognitive science. This article outlines his contributionsto Artificial Intelligence, connectionism, hypercomputation, andArtificial Life, and also describes Turing's pioneering role in thedevelopment of electronic stored-program digital computers. It locatesthe origins of Artificial Intelligence in postwar Britain. It examinesthe intellectual connections between the work of Turing and ofWittgenstein in respect of their views on cognition, on machineintelligence, and on the relation between provability and truth. Wecriticise widespread and influential misunderstandings of theChurch–Turing thesis (...) and of the halting theorem. We also explore theidea of hypercomputation, outlining a number of notional machines thatcompute the uncomputable. (shrink)

Turing’s paper on computable numbers has played its role in underpinning different perspectives on the world of information. On the one hand, it encourages a digital ontology, with a perceived flatness of computational structure comprehensively hosting causality at the physical level and beyond. On the other, it can give an insight into the way in which higher order information arises and leads to loss of computational control—while demonstrating how the control can be re-established, in special circumstances, via suitable type reductions. (...) We examine the classical computational framework more closely than is usual, drawing out lessons for the wider application of information–theoretical approaches to characterizing the real world. The problem which arises across a range of contexts is the characterizing of the balance of power between the complexity of informational structure and the means available to bring this information back into the computational fold. We proceed via appropriate mathematical modelling to a more coherent view of the computational structure of information, relevant to a wide spectrum of areas of investigation. (shrink)