Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one-tape computable, and so the two (...) models of infinitary computation are not equivalent. Surprisingly, the class of one-tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal that is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals. (shrink)

In [7], open questions are raised regarding the computational strengths of so-called ∞-α -Turing machines, a family of models of computation resembling the infinite-time Turing machine model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals (...) α such that Tα≻TωTα≻Tω, the smallest of which is precisely γ , the supremum of ordinals clockable by TωTω. In fact, there is a hierarchy of countable TαTαs of increasing strength corresponding to the transfinite Turing-jump operator ▼. There is a countable ordinal μ such that neither Tμ⪰Tω1Tμ⪰Tω1 nor Tμ⪯Tω1Tμ⪯Tω1—that is, the models TμTμ and Tω1Tω1 are computation-strength incommensurable . A similar fact holds for any larger uncountable device replacing Tω1Tω1. Further observations are made about countable TαTα. (shrink)

A true Turing machine requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime, but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar to our world. But curiously (...) enough-and this is the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation, a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

A true Turing machine (TM) requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime (the spacetime of common sense), but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are (...) similar ("close") to our world. But curiously enough-and this is the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation (e.g. intuitive, finitely programmed, limited in computational capability), a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

soft servants of durable material: they live without pretension in complicated relays and electrical circuits. Speed, docility are their strength. One asks: “What is 2 × 2?”—“Are you a machine?” They answer or refuse to answer, depending on what you demand. There are, however, other machines as well, more abstract automatons, bolder and more inaccessible, which eat their tape in mathematical formulae. They imitate in language. In infinite loops, farther and farther back in their retreat towards more subtle (...) algorithms, more recursive functions. They are logical and describe themselves. As when a man with a hand-mirror pressed against his nose in front of a mirror sees in infinite rows the same image multiplied in a shrinking, darkening corridor of glass. It is a Gödel theorem as good as any. He sees infinity, but what he does not see is his face. (From Göran Printz-Påhlson´s poem “The Turing Machine” published in Säg minns du skeppet Refanut? Samlade dikter 1950–1983 (1984) Bonniers, Stockholm). (shrink)

Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only (...) if the content of that cell has stabilized before that limit step and is then equal to this constant value. We call these machines weak infinite time Turing machines. We study different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. We show that some of these models are equivalent to each other concerning their computational strength. We show that wITTMs decide exactly the arithmetic relations on natural numbers. (shrink)

The tape is divided into squares, each square bearing a single symbol—'0' or '1', for example. This tape is the machine's general-purpose storage medium: the machine is set in motion with its input inscribed on the tape, output is written onto the tape by the head, and the tape serves as a short-term working memory for the results of intermediate steps of the computation. The program governing the particular computation that the machine is to perform is also (...) stored on the tape. A small, fixed program that is 'hard-wired' into the head enables the head to read and execute the instructions of whatever program is on the tape. The machine's atomic operations are very simple—for example, 'move left one square', 'move right one square', 'identify the symbol currently beneath the head', 'write 1 on the square that is beneath the head', and 'write 0 on the square that is beneath the head'. Complexity of operation is achieved by the chaining together of large numbers of these simple atoms. Any universal Turing machine can be programmed to carry out any calculation that can be performed by a human mathematician working with paper and pencil in accordance with some algorithmic method. This is what is meant by calling these machines 'universal'. (shrink)

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there (...) has been theorisation that all physical systems can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

Using infinite time Turing machines we define two successive extensions of Kleene’s ${\mathcal{O}}$ and characterize both their height and their complexity. Specifically, we first prove that the one extension—which we will call ${\mathcal{O}^{+}}$ —has height equal to the supremum of the writable ordinals, and that the other extension—which we will call ${\mathcal{O}}^{++}$ —has height equal to the supremum of the eventually writable ordinals. Next we prove that ${\mathcal{O}^+}$ is Turing computably isomorphic to the halting problem of (...) class='Hi'>infinite time Turing computability, and that ${\mathcal{O}^{++}}$ is Turing computably isomorphic to the halting problem of eventual computability. (shrink)

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for (...) the concept of a Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Philosophy and Rhetoric 35.2 (2002) 153-174 [Access article in PDF] LSDNA: Rhetoric, Consciousness Expansion, and the Emergence of Biotechnology Richard Doyle I had to struggle to speak intelligibly. —Albert Hofmann on his self-experiment with LSD-25 Finding a place to start is of utmost importance. Natural DNA is a tractless coil, like an unwound and tangled audio tape on the floor of the car in the dark. —Kary Mullis on (...) the invention of Polymerase Chain Reaction 1. Undoing life What happened is this: Once upon a time there was a narrative of vitality. Ok, not a narrative, but an apprehension, a fear, a vision. It didn't have a beginning, middle, or end. It was. Its contours were no more determinable than those of consciousness. Indeed, our consciousness, as humans, was our sole alleged difference from it. From something called "life." We were more than life, but were also, tragically, confined to it. You know the story all too well. Some of its major authors were Cuvier, Lamarck, Darwin, Bichat. Even Shelley.Just because this sudden transformation happened on paper doesn't mean it was easy to endure. Enormous numbers of humans went on tranquilizers just to deal with the effects. Others, elsewhere, knew nothing but rumors. Nonetheless, they became increasingly implicated in its effects, the effects of understanding and experiencing both "life" and "consciousness" as informatic events. Suddenly—and it is sudden, a real surprise—both our vitality and our thought were distributed, scattered across a network and nowhere in particular. Timothy Leary and Francis Crick were speaking the same language, the language of information where the organic and the machinic enfold each other helically and, sometimes, the capacity for replication goes through the ceiling. This new language of information would [End Page 153] introduce a novel response and abyss: the pleasures and hells of eternal replication. The distribution of both life and consciousness enabled a dream of immortality from which we have not yet awakened, as the mere specter of infinite clonal replicants provokes entropies of identity even as it preserves the self from onslaughts of decay. 1In at least one of its characteristics this shift toward an informatic understanding of life is perhaps not really so novel. The seductions of control are hardly, historians of science tell us, foreign to the practices and effects of technoscience. Evelyn Fox Keller makes this point concisely and precisely in her not-quite eponymous essay, "From Secrets of Life to Secrets of Death," itself a self-professed sequel to her 1986 "Making Gender Visible." Here the scientific "impulse" is underwritten by a perennial motif that underlies much of scientific creativity, namely, the urge to fathom the secrets of nature and the collateral hope that, in fathoming the secrets of nature, we will fathom (and hence gain control of) our own mortality (Secrets, 29).Surely Keller is correct that the nascent practices of molecular biology were cryptographic in character, an espionage project unknowingly launched by Erwin Schrodinger during the Second World War. Surely it is crucial to this moment that while Schrodinger's 1943 Dublin lectures were introducing audiences to the concept of the code-script, Alan Turing again brilliantly decrypted a modified U-boat code, giving the Allies code superiority for the remainder of the war. 2 But in this segment on that strange growth called "biotechnology," I want to focus on what Keller has called the "collateral" of hope in this cryptographic impulse, namely the collateral equation between inquiry and control, specifically the control of mortality.For is "fathoming" a secret identical to the exercise of control? The very cadence and rhetorical encryption of Keller's formulation here, a general parenthetical syllogistic conclusion within and alongside a hyphenated invocation of particularity, suggest that concepts and practices of secrecy are more unstable than Keller implies with her invocation of Feynman's "disease" of lock picking: "One of my diseases, one of my things in life, is that anything that is secret, I try to undo" (40).For Keller, Feynman's confession is emblematic of a desire to control life and death... (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Everyset. for example, is decidable by such machines, and the semi-decidable sets form a portion of thesets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible (...) hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L ζ -stables. It also implies that the machines devised are "Σ 2 Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

We obtain a large class of significant examples of n-random reals (i.e., Martin-Löf random in oracle $\varphi ^{(n - 1)} $ ) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set O ⊆(ℕ). In particular, we develop methods to transfer $\Sigma _n^0 $ or $\Pi _n^0 $ or (...) many-one completeness results of index sets to n-randomness of associated probabilities. (shrink)

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down $\zeta$, the least ordinal not the length of any eventual output of an Infinite Time Turing machine ; using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further (...) that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L$_\zeta$-stables. It also implies that the machines devised are "$\Sigma_2$ Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Reviewed by:Ad Infinitum: The Ghost in Turing’s Machine: Taking God Out of Mathematics and Putting the Body Back InTony E. JacksonAd Infinitum: The Ghost in Turing’s Machine: Taking God Out of Mathematics and Putting the Body Back In, by Brian Rotman; xii & 203 pp. Stanford: Stanford University Press, 1993, $39.50 cloth, $12.95 paper.Brian Rotman’s book attempts to pull mathematics—the last, most solid home of (...) metaphysical thought—off its absolutist foundations and into the roiling current of postmodernism. His argument works in what has by now become a rather standard manner. He shows how the grounding ideas of mathematics rest upon the insupportable assumption of a realm of absolute truth, “truth perfect, truth outside time, outside space, outside the material world of matter, energy, and entropy, truth somehow able to be discovered or apprehended but never invented” (p. 19). Rotman questions this Platonic grounding in a number of ways.First, with the help of linguistics (de Saussure, Benveniste, Wittgenstein, and Peirce) he provides a semiotic analysis of mathematical arguments as real-world linguistic events. Proof he looks at “not as a form of inference engaged in preserving eternal truths, but as an historically conditioned species of rhetoric” (p. 35). Secondly, Rotman argues that one idea has most secured the fortress-like solidity of mathematical Platonism: the idea of ad infinitum or infinite iteration. Mathematics takes off from the givenness of the natural numbers, our everyday 1, 2, 3 and so on to infinity. It is the “so on to infinity” that frames up the house of arithmetic as it has stood since Euclid. (Euclidean in this context is equivalent to Platonic in the context of philosophy.) But what is the referent of these numbers? Ultimately they are said to be the symbolic representation of the action of counting, which is the “mathematical ur-cognition” (p. 51). And yet we cannot imagine any material human situation in which counting could actually go on to infinity. Therefore, some impossible, supernatural agent (the ghost of the title) must be projected in order for this conception to exist. Similarly, Rotman argues against the assumption of “perfect repeatability” because this notion depends upon some purely imaginary, ideal identity of object or action that could possibly be repeated. Ad infinitum requires and assumes both a disembodied, metaphysical counter and a disembodied, metaphysical counted.So Rotman sets about putting the body back into this symbolic system by rejecting the idea of ad infinitum. Instead of assuming the existence of counting activities that run, in principle, out to infinity without changing their nature, Rotman posits what he calls “realizable iteration,” that is, counting that admits the necessary dissolution or change of whatever repetitive function you begin with. Put simply, he includes the fact that quantitative accumulation or repetition always eventually brings about a qualitative change: at some point in everyday life a difference of degree of the “same” thing or action inevitably becomes a difference of kind. The natural numbers and the ad infinitum [End Page 390] remain blissfully sheltered from this inescapable real world truth, but Rotman reformulates mathematics so as to include this truth in the very idea of numbering.In fact (and he acknowledges this) he theorizes counting after the model of chaos or complexity theory in the physical sciences. Realizable iteration, he says, will bring in the “qualitative differences” forgotten or repressed (the language of Nietzsche, Heidegger, and Freud runs throughout) in the metaphysical version of number, and “display [the qualitative differences] as the emergent effects of repetition” (p. 131). Even numerical addition, for instance, which had been the most linearly continuous of activities, now will be linear beginning from some initial point, but will become increasingly nonlinear as quantitative increase tends towards some point of qualitative discontinuity with what had come before. The point of discontinuity, though certain to appear, is by its nature not specifiable beyond a horizon of probability, and in this, Rotman aligns his arithmetic not only with chaos theory, but also with quantum mechanics. In an appendix, Rotman elaborates at least to a degree the “pre-elements” of his non-Euclidean arithmetic.As chaos theory does not destroy everyday cause... (shrink)

Pattern recognition is represented as the limit, to which an infinite Turing process converges. A Turing machine, in which the bits are substituted with qubits, is introduced. That quantum Turing machine can recognize two complementary patterns in any data. That ability of universal pattern recognition is interpreted as an intellect featuring any quantum computer. The property is valid only within a quantum computer: To utilize it, the observer should be sited inside it. Being outside (...) it, the observer would obtain quite different result depending on the degree of the entanglement of the quantum computer and observer. All extraordinary properties of a quantum computer are due to involving a converging infinite computational process contenting necessarily both a continuous advancing calculation and a leap to the limit. Three types of quantum computation can be distinguished according to whether the series is a finite one, an infinite rational or irrational number. (shrink)

A set theory model of reality, representation and language based on the relation of completeness and incompleteness is explored. The problem of completeness of mathematics is linked to its counterpart in quantum mechanics. That model includes two Peano arithmetics or Turing machines independent of each other. The complex Hilbert space underlying quantum mechanics as the base of its mathematical formalism is interpreted as a generalization of Peano arithmetic: It is a doubled infinite set of doubled Peano arithmetics having (...) a remarkable symmetry to the axiom of choice. The quantity of information is interpreted as the number of elementary choices (bits). Quantum information is seen as the generalization of information to infinite sets or series. The equivalence of that model to a quantum computer is demonstrated. The condition for the Turing machines to be independent of each other is reduced to the state of Nash equilibrium between them. Two relative models of language as game in the sense of game theory and as ontology of metaphors (all mappings, which are not one-to-one, i.e. not representations of reality in a formal sense) are deduced. (shrink)

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a generally infinite family of numbers looks straightforward, at first glance, examples for which this maximum exists seem to be very rare. It is the main purpose of this paper to prove (...) that, nevertheless, the definition has a large number of important applications. Using the framework of TTE [40], we introduce computable metric spaces and computability on the compact subsets. We prove that every computable metric space has a c-proper c-admissible representation. We prove that Turing machine time complexity of a function computable relative to c-admissible c-proper representations has a computable bound on every computable compact subset. We prove that computably compact computable metric spaces have concise c-proper c-admissible representations and show by examples that many canonical representations are of this kind. Finally, we compare our definition with a similar one by Labhalla et al. [22]. Several examples illustrate the concepts. By these results natural and realistic definitions of computational complexity are now available for a variety of numerical problems such as image processing, integration, continuous Fourier transform or wave propagation. (shrink)

In his article “On Mechanical Recognition” R. J. Nelson brings to bear a branch of mathematical logic called automata theory on problems of artificial intelligence. Specifically he attacks the anti-mechanist claim that “[i]nasmuch as human recognition to a very great extent relies on context and on the ability to grasp wholes with some independence of the quality of the parts, even to fill in the missing parts on the basis of expectations, it follows that computers cannot in principle be programmed (...) to recognize or learn to recognize all patterns”, p. 24). Nelson proposes, contrary to this claim, that “gestalt recognition is not beyond digital automata”. in particular, he claims, he will establish by what he calls “Turing machine arguments” that the following four theses are true: automata can recognize different pattern types in one and the same set of instances;automata can recognize the “same” pattern in different sets of instances;automata can recognize incomplete, degraded patterns having missing or indeterminate parts;automata can recognize family resemblances. (shrink)

Natural argument is represented as the limit, to which an infinite Turing process converges. A Turing machine, in which the bits are substituted with qubits, is introduced. That quantum Turing machine can recognize two complementary natural arguments in any data. That ability of natural argument is interpreted as an intellect featuring any quantum computer. The property is valid only within a quantum computer: To utilize it, the observer should be sited inside it. Being outside (...) it, the observer would obtain quite different result depending on the degree of the entanglement of the quantum computer and observer. All extraordinary properties of a quantum computer are due to involving a converging infinite computational process contenting necessarily both a continuous advancing calculation and a leap to the limit. Three types of quantum computation can be distinguished according to whether the series is a finite one, an infinite rational or irrational number. -/- . (shrink)

Infinite machines (IMs) can do supertasks. A supertask is an infinite series of operations done in some finite time. Whether or not our universe contains any IMs, they are worthy of study as upper bounds on finite machines. We introduce IMs and describe some of their physical and psychological aspects. An accelerating Turing machine (an ATM) is a Turing machine that performs every next operation twice as fast. It can carry out infinitely many operations (...) in finite time. Many ATMs can be connected together to form networks of infinitely powerful agents. A network of ATMs can also be thought of as the control system for an infinitely complex robot. We describe a robot with a dense network of ATMs for its retinas, its brain, and its motor controllers. Such a robot can perform psychological supertasks - it can perceive infinitely detailed objects in all their detail; it can formulate infinite plans; it can make infinitely precise movements. An endless hierarchy of IMs might realize a deep notion of intelligent computing everywhere. (shrink)

We first discuss Michael Dummett’s philosophy of mathematics and Robert Brandom’s philosophy of language to demonstrate that inferentialism entails the falsity of Church’s Thesis and, as a consequence, the Computational Theory of Mind. This amounts to an entirely novel critique of mechanism in the philosophy of mind, one we show to have tremendous advantages over the traditional Lucas-Penrose argument.

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I (...) present a more mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable. (shrink)

We define a program size complexity function $H^\infty$ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in ${\{0,1\}}^\omega$ relative to the $H^\infty$ complexity. We prove that the classes of Martin-Löf random sequences and $H^\infty$-random sequences coincide and that the $H^\infty$-trivial sequences are exactly the recursive ones. We also study some properties of $H^\infty$ and compare it with other complexity functions. In particular, (...) $H^\infty$ is different from $H^A$, the prefix-free complexity of monotone machines with oracle A. (shrink)

Some regularities enjoy only an attenuated existence in a body of training data. These are regularities whose statistical visibility depends on some systematic recoding of the data. The space of possible recodings is, however, infinitely large – it is the space of applicable Turing machines. As a result, mappings that pivot on such attenuated regularities cannot, in general, be found by brute-force search. The class of problems that present such mappings we call the class of “type-2 problems.” Type-1 problems, (...) by contrast, present tractable problems of search insofar as the relevant regularities can be found by sampling the input data as originally coded. Type-2 problems, we suggest, present neither rare nor pathological cases. They are rife in biologically realistic settings and in domains ranging from simple animat behaviors to language acquisition. Not only are such problems rife – they are standardly solved! This presents a puzzle. How, given the statistical intractability of these type-2 cases, does nature turn the trick? One answer, which we do not pursue, is to suppose that evolution gifts us with exactly the right set of recoding biases so as to reduce specific type-2 problems to type-1 mappings. Such a heavy-duty nativism is no doubt sometimes plausible. But we believe there are other, more general mechanisms also at work. Such mechanisms provide general strategies for managing problems of type-2 complexity. Several such mechanisms are investigated. At the heart of each is a fundamental ploy – namely, the maximal exploitation of states of representation already achieved by prior, simpler learning so as to reduce the amount of subsequent computational search. Such exploitation both characterizes and helps make unitary sense of a diverse range of mechanisms. These include simple incremental learning, modular connectionism, and the developmental hypothesis of “representational redescription”. In addition, the most distinctive features of human cognition – language and culture – may themselves be viewed as adaptations enabling this representation/computation trade-off to be pursued on an even grander scale. (shrink)

The Busy Beaver Competition is held by Turing machines. The better ones halt taking much time or leaving many marks, when starting from a blank tape. In order to understand the behavior of some Turing machines that were once record holders in the five-state Busy Beaver Competition, we analyze their halting problem on all inputs. We prove that the halting problem for these machines amounts to a well-known problem of number theory, that of the behavior of the repeated (...) iteration of Collatz-like functions, that is functions defined by cases according to congruence classes. (shrink)

Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection (...) on how quantum computer might implement the idea of "infinite calculation" is the main subject. (shrink)

An infinite lottery machine is used as a foil for testing the reach of inductive inference, since inferences concerning it require novel extensions of probability. Its use is defensible if there is some sense in which the lottery is physically possible, even if exotic physics is needed. I argue that exotic physics is needed and describe several proposals that fail and at least one that succeeds well enough.

Two very different insights motivate characterizing the brain as a computer. One depends on mathematical theory that defines computability in a highly abstract sense. Here the foundational idea is that of a Turing machine. Not an actual machine, the Turing machine is really a conceptual way of making the point that any well-defined function could be executed, step by step, according to simple 'if-you-are-in-state-P-and-have-input-Q-then-do-R' rules, given enough time (maybe infinite time) [see COMPUTATION]. Insofar as (...) the brain is a device whose input and output can be characterized in terms of some mathematical function -- however complicated -- then in that very abstract sense, it can be mimicked by a Turning machine. Given what is known so far brains do seem to depend on cause-effect operations, and hence brains appear to be, in some formal sense, equivalent to a Turing machine [see CHURCH-TURING THESIS]. On its own, however, this reveals nothing at all of how the mind-brain actually works. The second insight depends on looking at the brain as a biological device that processes information from the environment to build complex representations that enable the brain to make predictions and select advantageous behaviors. Where necessary to avoid ambiguity, we will refer to the first notion of computation as algorithmic computation, and the second as information processing computation. (shrink)

The uniform halting problem (UH) can be stated as follows:Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID).An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [4, p. 118]) we assume that in an ID the tape must be blank except for some finite number of squares. If we remove this (...) restriction the UH becomes the immortality problem (IP). (shrink)

Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n2 is a lower bound and this is optimal in (...) two cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. (shrink)

Two very different insights motivate characterizing the brain as a computer. One depends on mathematical theory that defines computability in a highly abstract sense. Here the foundational idea is that of a Turing machine. Not an actual machine, the Turing machine is really a conceptual way of making the point that any well-defined function could be executed, step by step, according to simple 'if-you-are-in-state-P-and-have-input-Q-then-do-R' rules, given enough time (maybe infinite time) [see COMPUTATION]. Insofar as (...) the brain is a device whose input and output can be characterized in terms of some mathematical function -- however complicated -- then in that very abstract sense, it can be mimicked by a Turning machine. Given what is known so far brains do seem to depend on cause-effect operations, and hence brains appear to be, in some formal sense, equivalent to a Turing machine [see CHURCH-TURING THESIS]. On its own, however, this reveals nothing at all of how the mind-brain actually works. The second insight depends on looking at the brain as a biological device that processes information from the environment to build complex representations that enable the brain to make predictions and select advantageous behaviors. Where necessary to avoid ambiguity, we will refer to the first notion of computation as. (shrink)

In lieu of an abstract, here is a brief excerpt of the content: Reviewed by: The Myth or Elegy of Artificial Intelligence by Tingyang ZhaoXuejian Zhou (bio)Rengongzhineng de shenhua huo beige 人工智能的神話或悲歌 ( The Myth or Elegy of Artificial Intelligence). By Tingyang Zhao 趙汀陽. Beijing: The Commercial Press, 2022. Pp. 155. Hardcover RMB68, isbn 978-981-16-7749-6. In recent years, the philosophy of artificial intelligence has undoubtedly become one of the most popular topics. There is a vague viewpoint suggesting that Chinese philosophy (...) might face challenges in addressing the philosophical issues posed by artificial intelligence. However, compared to the past, when discussing Chinese philosophy today, we must acknowledge the significant impact of modern technology. While the contemporary world does indeed witness clashes of civilizations, individuals from various civilizations share a common predicament: their close entanglement with modern technology. Regarding the future of Chinese philosophy, it becomes crucial to direct our attention towards modern advancements like artificial intelligence and the diverse range of issues they introduce. In light of this context, Zhao Tingyang's 趙汀陽 new book, The Myth or Elegy of Artificial Intelligence, presents us with a fresh perspective. In this book, Zhao primarily delves into the philosophical issues surrounding Super Artificial Intelligence, a subject regarded as both a metaphysical and a political problem. This notion refers to artificial intelligence that surpasses general artificial intelligence in terms of functionality, and possesses self-consciousness. Therefore, "myth" refers to the myth of the emergence of Super Artificial Intelligence disrupting people's subjectivity, giving rise to a new myth of artificial intelligence. Conversely, the term "elegy" embodies the crisis in human destiny that stems from such profound changes, which will lead to an ontological revolution in human existence. This suggests that within the narrative of artificial intelligence's myth, there lies the elegy of humanity (p. 4). The intricate interplay between these two realms of myth and elegy vividly showcases the value of Chinese philosophy. The book consists of a total of ten chapters. In Chapter 1, Zhao initially presents a thought-provoking question. With the rapid advancement of artificial intelligence humanity is faced with a novel ontological event, where the existence of artificial intelligence could potentially jeopardize human existence. This presents an ontological problem of "de-existence" (p. 8). As current artificial intelligence remains within the domain of the Turing machine concept and lacks subjectivity, it cannot effectively engage in matters involving self-correlation or [End Page 1] infiniteness. However, if artificial intelligence evolves into a super Turing machine endowed with subjectivity and free will, it could gain the capacity to modify its own programs and societal norms based on its needs or maximal benefits. This scenario introduces the possibility of a crisis in human existence, where the very existence of humanity is put at risk (pp. 17-23). In Chapter 2, Zhao analyzes the safety conditions of artificial intelligence and proposes the need to establish self-destruct mechanisms for Super Artificial Intelligence to ensure the status of human existence (pp. 34-38). Interestingly, in this context, Zhao connects artificial intelligence with the concept of Tianxia 天下 ("all under heaven"), implying that in order to control capital and power, the world needs a new form of politics, namely, a Tianxia 天下 system. Tianxia 天下 represents a world system that ensures world peace and the shared interests of people in a multicultural context, a non-exclusive system defining the world beyond any particular entity. According to Zhao, only a Tianxia 天下 system can manage the technological risks of the world (p. 39). Theoretically (hopefully in practice as well), a significant application of the Tianxia 天下 system would be to use global authority to limit any high-risk behaviors. Based on the first two chapters, it becomes apparent that the dangers related to artificial intelligence do not lie in its current capabilities, but in its potential for self-consciousness. For this reason, in Chapter 3, Zhao analyzes this issue further. In his view, once artificial intelligence possesses the ability for self-reflection, it will become possible for it to transform its own system and create new rules. Especially if artificial intelligence invents a universal language of its own, equivalent to human natural language, then all program systems could be reinterpreted, reconstructed, and redefined using this universal language (pp. 47-52). Furthermore, if... (shrink)

We describe in some detail how to build an infinite computing machine within a continuous Newtonian universe. The relevance of our construction to the Church-Turing thesis and the Platonist-Intuitionist debate about the nature of mathematics is also discussed.

Turing’s much debated test has turned 70 and is still fairly controversial. His 1950 paper is seen as a complex and multilayered text, and key questions about it remain largely unanswered. Why did Turing select learning from experience as the best approach to achieve machine intelligence? Why did he spend several years working with chess playing as a task to illustrate and test for machine intelligence only to trade it out for conversational question-answering in 1950? Why (...) did Turing refer to gender imitation in a test for machine intelligence? In this article, I shall address these questions by unveiling social, historical and epistemological roots of the so-called Turing test. I will draw attention to a historical fact that has been only scarcely observed in the secondary literature thus far, namely that Turing’s 1950 test emerged out of a controversy over the cognitive capabilities of digital computers, most notably out of debates with physicist and computer pioneer Douglas Hartree, chemist and philosopher Michael Polanyi, and neurosurgeon Geoffrey Jefferson. Seen in its historical context, Turing’s 1950 paper can be understood as essentially a reply to a series of challenges posed to him by these thinkers arguing against his view that machines can think. Turing did propose gender learning and imitation as one of his various imitation tests for machine intelligence, and I argue here that this was done in response to Jefferson's suggestion that gendered behavior is causally related to the physiology of sex hormones. (shrink)

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time (...) is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}$ sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not ${n \in r}$ with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs. (shrink)

In this paper we discuss the views on the Turing test of four influential thinkers who belong to the tradition of analytic philosophy: Ludwig Wittgenstein, Noam Chomsky, Hilary Putnam and John Searle. Based on various beliefs about philosophical and/or linguistic matters, they arrive at different assessments of both the significance and suitability of the imitation game for the development of cognitive science and AI models. Nevertheless, they share a rejection of the idea that one can treat Turing test (...) as a test for “machine thinking.” This seems to stem from a concern for the proper use of language —one that is a fundamental methodological commitment of analytic philosophy. (shrink)

This is the first of two volumes of essays on the intellectual legacy of Alan Turing, whose pioneering work in artificial intelligence and computer science made him one of the seminal thinkers of the century. A distinguished international cast of contributors focus on the three famous ideas associated with his name: the Turing test, the Turing machine, and the Church-Turing thesis. 'a fascinating series of essays on computation by contributors in many fields' Choice.

Mahadevan proposes that we are at the cusp of imagination science, one of whose primary concerns will be the design of imagination machines. Programs have been written that are capable of generating jokes, producing line-drawings that have been exhibited at such galleries as the Tate, composing music in several styles reminiscent of such greats as Vivaldi and Mozart, proving geometry theorems, and inducing quantitative laws from empirical data. In recent years, Dartmouth has been hosting Turing Tests in creativity in (...) three categories: short stories, sonnets, and dance music DJ sets. In this post, I will provide a brief and non-exhaustive survey of some plausible responses to these imagination machines and the related prospects for our understanding of the imagination. (shrink)