A mathematical model of quantum computer by both arithmetic and set theory Vasil Penchev, vasildinev@gmail.com Bulgarian Academy of Sciences: Institute of Philosophy and Sociology: Dept. of Logical Systems and Models INTRODUCTION A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I. Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them. Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as "language" therefore including metaphors as mappings different than representation. Section III investigates that formal relation of "reality", "representation", and "language" modeled by (at least two) Turing machines. The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV. Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics, on the one hand, and allowing of practical implementations. I COMPLETENESS IN MATHENATICS AND QUANTUM MECHANICS Cantor's set theory involved actual infinity. However, many paradoxes directly or indirectly linked to the concept of infinite set were found. One of the first was Russell's (Russell 1902). Hilbert suggested his program for the foundation of set theory and all mathematics on arithmetic (Hilbert 1931; Kreisel 1958). Thus the "consistent part of actual infinity" in set theory should be reduced to that of finite natural numbers as the auxiliary notion of any finite number having some property if any that exists, i.e. utilizing the "εε-symbol" (Hilbert, Bernays 1970), or "potential infinity" seen as any indefinite finiteness. Nevertheless, Gödel (1931) has managed to show that neither any formal system containing Peano (1889) arithmetic neither the arithmetic itself can be both complete and consistent. The result of Gödel is crucial for the philosophy of mathematics (Bazhanov1993). In fact, Peano (1889)'s axioms had inspired (Gunderson 2011: 22; Peano 1889: 5) by Dedekind (1888)'s foundation of the natural numbers on set theory and especially on the wellElectronic copy available at: https://ssrn.com/abstract=3638937 ordering of an infinite set1. Mathematical induction is crucial among Peano's axioms: It is neither provable in type theory (Royse 1969) nor explanatory (Lange 2009). Furthermore, at least two different enough types of consistent proofs immediately referring to the consistency of Peano arithmetic appeared (Gentzen 1936; 1938; Smorynski 1973; Kanckos 2010). Both were interpreted by Gödel in his works (Gödel [1938]; Gödel 1958: Tait 2005; 2010). Almost at the same time, a physical and thus experimental science, quantum mechanics met the problem of completeness for the hypothesis of the so-called hidden variables (Einstein, Podolsky, Rosen 1935). In fact, it as well as Schrödinger's study (also 1935) forecast the phenomena of entanglement on the base of Hilbert space. A few theorems (Neumann 1932: 167173; Kochen and Specker 1968) were deduced from the mathematical formalism of quantum mechanics, namely the infinitely dimensional complex Hilbert space. Bell (1964) demonstrated how the hypothesis of hidden variable might be tested experimentally. The corresponding experiments (Clauser, Horne 1974; Aspect, Grangier, Roger 1981; 1982) and many, many others after that categorically show that no hidden variables in quantum mechanics, and consequently it is complete. The key for the validity of Gödel (1931)'s result to Hilbert's program is within the former itself and even within its core: that statement [RR(qq); qq] stating to be false. Its approach can be described as skeptical to finitism (Resnik 1974: 145), but it can be referred to itself generating a kind of skepticism about the skepticism in turn. Furthermore, Hilbert's program can be relevantly modified after re-estimating the meaning of Gödel incompleteness (Murawski 1999: 303-323). Gödel has written (1931: 175 [footnote 14]) that any antinomy, e.g. that of Liar (even mentioned expressly by Gödel ibidem), can serve to construct the proof of incompleteness. Gödel's proof depends crucially on the disjunctive distinction between level and meta-level in the statement [RR(qq); qq]: This is an observation, which had utilized by Russell in his theory of types (Principia [both editions]: 63[I]; 60[II]). One can "unfold" the Liar paradox into Yablo (1993)'s paradox: Both share the "fixed point structure" (Priest 1997: 242). Then if one suggests the "relativeness of the concept of set" (Skolem [1922]) and therefore not only that of different "inifinities", but not less also that of finiteness and infinity2, the transition between finiteness and infinity will need an analogical jump. The difference in the conditions of Gödel's incompleteness and Gentzen's completeness is crucial (Horská 2014). In other words, the problem is to be localized that specific element, to which the opposite result in each of both case is due: As the primitive recursive functions in Gentzen (1936 and 1938)'s approach are equivalent to Peano arithmetic being just all possible calculations in Peano arithmetic, the single added condition is transfinite induction in comparison to Gödel's opposite result. Furthermore, transfinite induction cannot be proved in Peano arithmetic (Gentzen 1943) therefore being an independent additional condition3. 1 Dedekind used different terms and definitions and the correspondence to ours can be only incomplete. 2 "Sogar die Begriffe "endlich", "unendlich", "einfach unendliche Reihe" usw. werden nur relativ innerhalb der axiomatischen Mengenlehre" (Skolem 1970[1922]: 143). 3 By the way, transfinite induction is not necessary for the consistency proof of a system of Turing machines (Caporaso 1978). Electronic copy available at: https://ssrn.com/abstract=3638937 Transfinite induction can be relevantly defined even within Peano arithmetic (Sommer 1995) as well as ordinals and the corresponding fixed points investigated (Jäger 1993). Thus nonstandard models are also definable in it (Ikeda, Tsuboi 2007). Gentzen himself linked his approach for proving completeness to Hilbert's finitism (Sieg 2012; Gentzen 1954) and intuitionism (Gentzen 1974; 1974a). The well-orderings of transfinite induction can be rather naturally linked to intuitionist theories (Howard, Kreisel 1966; Scarpellini 1969; 1972; Friedman, Sčedrov 1985). Bar induction can be seen as a two dimensional induction in virtue of the bar theorem4 (Kleene, Vesley 1965: 4351). Bar induction added to constructive ZFC can prove a kind of consistency of set theory (Rathjen 2006). The second-dimensional Peano arithmetic copes with the argument of diagonalization (Montagna 1980) restoring it from one-dimensional Gödel's use to the initial two-dimensional Cantor's use. Indeed, Heyting arithmetic is also complete in an exact sense (Visser 1982; Kanckos 2010) just as Gentzen's approach to Peano arithmetic can be discussed as a proof of completeness. The so-called Dialectica interpretation of Heyting arithmetic by Gödel (1958) is analogical in a sense. As to the origin of the incompleteness problem in quantum mechanics, one may mean the following: Gödel and Einstein are both Jews, refugees from Nazism, and even close friends in Princeton (Yourgrau 2006). However, Gödel came to Princeton in 1940. The famous triple article of Einstein, Podolsky, and Rosen "Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?" was published in 1935. The complex Hilbert space implies the absence of hidden variables (Neumann 1932: 167-173; Kochen, Specker 1968) and thus the completeness of quantum mechanics. One can demonstrate that Hilbert's par excellence finitist idea about εε-symbol (Hilbert, Bernays 1970: 9-18) as well interpretable as partly equivalent to Gentzen's transfinite induction (Kreisel, 1958a; Zach 2003; Towsner 2005) corresponds to the complementation of Peano arithmetic with choice: The ε-symbol contents that choice if a given number exists or not: II TURING MACHNINES One can summarize that the incompleteness of any finiteness and thus finiteness at all is divided from the completeness of infinity only by a single step, but forever by a step. That impossible step is represented and named differently in the mentioned above approaches to completeness. Nevertheless, its essence remains always to be anything else beyond finiteness, or finiteness complemented by a gap. That gap in turn can be always represented as a second dimension of finiteness and thus as a second finiteness. Furthermore, finiteness at all can be well modeled as Peano arithmetic, and that gap by a second dimension of it or as a second and absolutely independent Peano arithmetic necessary for the first one to be complemented to completeness. 4 The two-dimensionality can be contrasted on the background of the one-dimensionality of the corresponding theorem (König 1927) in mathematics based on set theory. Electronic copy available at: https://ssrn.com/abstract=3638937 In the present section, the same result will be interpreted in terms of technically implementable models, those of Turing machines, i.e. computers. Turing (1936) suggests the idea that any calculation having a result and thus any action of a device such as a contemporary computer can be represented as a finite series of natural numbers, and any that series in turn as a finite series of binary choices, just the work of what is named today "Turing machine". Consequently, any that calculation is a finite subset of natural numbers therefore obeying Peano axioms and all possible calculations eventually including those, which cannot finish for any finite time, coincides with the set of all subsets of the Peano natural numbers. This hints that the Gödel (1931) result can be interpreted immediately as to Turing machines and even the statement [RR(qq); qq] stating (for itself) not to be true. In fact, that interpretation is "halting problem" (Turing 1936): a Turing machine cannot resolve the problem whether it can resolve or not any problem in a finite time. Thus the halting problem is an example of what divides any Turing machine from completeness. Many modifications of "Turing machines" have been suggested and explored whether they might resolve the halting problem. One can prove that some of them might, some of them might not. However, no modified Turing machine, which can resolve the halting problem therefore being in a sense complete, cannot be technically realized for it contains some pure mathematical concept such as infinity. Some of the explored modifications of Turing machine are those: working "discrete transfinite time" (Welsh 2009); knowing "their own Gödel-sentences" (Tennant 2001); making "binary social choice" in "an infinite society" (Tanaka 2008); with "self-replication" (Sayama 2008); "connected to the undecidability of the halting problem" (Pavlotskaya 2002); "non-erasing", which are on the "frontier between a decidable halting problem and universality" (Margenstern 1994); having "two types" (Maass et al 1993); having two states (Herman 1969); working "infinite time" (Hamkins, Seabold 2001; Lenzi, Monteleone 2004); being "generalized one-state Turing machines" (Herman 1969b); "with n-dimensional tape" (Herman 1968); and many, many others. Post (1936) describes the logical model of recursive process, which can be considered as a variant of Turing machine (De Mol 2006). A series of publications refer to that "Post machine" and the halting problem (Aanderaa, Fischer 1967). One can say that the above enumeration resembles Foucault (1966:7)'s famous re-citation via Borges from the Chinese encyclopedia about the kinds of animals right from "Les mots et les choses" translated in English as "The Order of Things": just Borges's quotation is that, of which "the book first arose out" (Foucault 1970: xiv). In fact, one of the main theses of Foucault about the "epistemic transformation" of knowledge by similarity to that by both identity and difference, right illustrated by the re-citation from Borges, corresponds directly to the transformation in the present paper from infinity to the units of identity and difference, i.e. the information binary units: the bits. The quoted publications belong to the huge set investigating the relation between the "halting problem" and "Turing machine" as by a kind of "eidetic reduction" of the latter as by that Electronic copy available at: https://ssrn.com/abstract=3638937 of the former (Hooper 1966; Fischer 1969; Bloom 1971; Herman 1969a; 1971; Selman 1974; Hay 1975; Pobedin, 1975; Shalyt-Margolin, Straznev, Tregubovich 2007; Gaβner 2008; Manin 2012). At least a few areas of research "beyond Turing machines", which are already embodied technically in our contemporary computers, can be outlined: Hyper-computation comprises as pure theoretical models including fundamentally unimplementable concepts, e.g. infinity, as technically realizable ones e.g. beyond the Church – Turing thesis and therefore exploring calculation beyond recursive functions (Siegelmann 1996; Copeland 2002; Stannett 1990; 2006). Human brain is an obvious example that there exists something real, which exceeds a contemporary computer unconditionally. Its nervous structure and functions might be interpreted by scientific models and even partly modeled in technical devices (Basti, Perrone 1889; 1995; Basti 2001). The concept of quantum information allows of reformulating quantum mechanics entirely in terms of information theory. Thus nature and the universe can be represented as a single huge calculating device, a quantum computer. The quantum computer (Benioff 1980; 1998; Feynman 1996; Deutsch 1885; 1989; Deutsch, Ekert, Lupacchini 2000; Mahler, Gemmer, Stollsteimer 2002; Nishimura, Ozawa 2009) is an area of investigation promising a fundamentally new generation of computers to be manufactured in the foreseeable future. The task of the present paper is not to suggest some new solving of the completeness problem particularly as to Turing machines, but rather to demonstrate that the problem coincides with its solution in a sense as both have one the same formal structure: that of an elementary choice, a bit of information. This can be illustrated by the representation of the complex Hilbert space underlying quantum mechanics and therefore quantum computers in terms of Peano arithmetic: First, the complex Hilbert space involves infinity at least in two independent and even symmetric ways: 1. It is infinitely dimensional: It can be discussed as a generalization of Peano arithmetic and even as two of those together with its dual space coinciding with it identically. Indeed it (or "both") can be represented as an infinite series of qubits, in each of which can be "recorded" two complex numbers (αα and ββ) such that |αα|2 + |ββ|2 = 1. If any qubit being a unit ball is shrunk to a point, and conventionally granting αα = 0 and ββ = 1, a Peano arithmetic will be obtained. So, its "rough structure" is representable as two complementary and therefore independent, but identical Peano arithmetics. 2. Each of its "axes" is infinite, two: It can be discussed as a generalization of the usual three-dimensional Euclidean geometry5 where furthermore any axis is complex and representable as a qubit. Thus it unlike the real Hilbert space does not suggest any well-ordering within any axis by itself, but only in virtue of the axiom of choice. So involving also its "fine structure", the complex Hilbert space is thinkable as a doubled countable set of uncountable continua. 5 A geometric approach to the foundation of mathematics has been an alternative at the turn of the XIX century (Tazzioli 2003). Electronic copy available at: https://ssrn.com/abstract=3638937 3. If the axiom of choice is applied, any qubit in turn is identifiable as the basic "rough stricture" of two independent Peano arithmetics; and vice versa: the "rough structure" without wellordering corresponds to any qubit (or its "fine structure"): The complex Hilbert space is perfectly symmetric in a sense including the axiom of choice. Second, what that perfect structure should describe adequately according to quantum mechanics is the system of the measured quantum system(s) and measuring device(s). Thus quantum mechanics, unlike classical one, needs a dual structure similar to that of any statistical thermodynamic theory consisting both of too many but very, very tiny microscopic elements and their large macroscopic system. Two incommensurable finiteneses turn out to be involved in thus: the one for the set of tiny elements with the quantity of action commeasurable with the Plank constant and the other for their common system with the macroscopic measuring device(s). III COMPLETENESS, LANGUAGE, REALITY, AND REPRESENTATION BY TURING MACHINES The relevant metaphor is that reality and its image in language "speak to each other" in a dialog in order to "agree with each other". Reality is just the state of "agreement", which is modeled by the state of equilibrium of the two computers. Language is modeled by reducing to any infinite countable set (AA) of its units of meaning, either words or propositions, or whatever others. That language is furthermore modeled in the computers in a few steps: – The units of meaning are reduced to the minimal possible ones, bits – The infinite countable set is modeled by the independence of the same pair of each other: – So: infinity is represented by its "gap" to finiteness just a second dimension. That infinite countable model of language includes all possible meanings, which can be ever expressed rather than the existing till now, which would always a finite set. This corresponds to the independence, the "gap" between the computers, which can be overcome by each of them only in an infinite set of working steps determining the value either "0" or "1" for each cell of an infinite "tape". However, the tandem of both, i.e. in dialog can overcome that gap in finite set of steps and thus, in finite time. The set-theory model can be also involved: The external twin of reality is introduced by another set (BB) such that its intersection with the above set of language to be empty. The union of them (CC = AA ∪ BB) exists always so that a one-to-one mapping (ff: CC ↔ AA) should exist under the condition of the axiom of choice The mapping (ff) produces an image (BB(ff)) of the latter set (BB) within the former set (AA). That image (BB (ff)) serves as the other twin of reality to model the reality within the language as the exact representation of that reality out of language (modeled as the set BB). One designates the image of BB into AA through f by "BB(ff)" so that BB(ff) is a true subset of AA. The necessity and sufficient condition of that representation between reality both within and out of the language is just the axiom of choice. Indeed, one needs only two well-ordered infinite series equivalent to the axiom of choice by the meditation of the so-called well-ordering theorem Electronic copy available at: https://ssrn.com/abstract=3638937 (or "principle"). The pair of the two Turing machines though each of them being finite can represent effectively the two infinite series by the relation of independence to each other. The axiom of choice should be situated between representation and metaphor. The relation between the sets BB(ff) and BB cannot be defined unambiguously if the axiom of choice does not hold. Then the vehicle between the two "twins" can be only metaphor. This corresponds to the case where the Turing machines depend partly on each other or share some infinite segment of their "tapes": Any operation of any of both machines within that segment is necessarily valid for the other one, and this is not true out of that segment. Two alternative, but equivalent approaches are further possible if one named the one Turing machine "reality", the other "representation: the image of reality in language", and their pair "language": 1. "Game of reality and its image": The computer "Reality" calculates "things", and "Representation" "words". The "things" and "words" are absolutely different from each other for both Turing machines, "Reality" and "Representation", are also absolutely independent of each other. Their game can be called "Naming". "Reality" calculates something, and "Representation" has to name it. "Reality" loses if it does not manage to create a following new thing, which is not in the list of already created. "Representation" loses if cannot give a new name of the lastly created new thing yet without any name. The game will generate a one-to-one mapping between "things" and "words" unlimitedly 2. "Language as ontology": One can suggest an initial state, "Paradise", where all things and words coincide and thus the two Turing machines, too. It implies the correct name of anything in definition: Then any of the two yet unnamed machines cannot lose in principle. However, that state is not stable. Any fluctuation in any of them will initiate the beginning of individuation, separation tending to the stable absolute independence of each other. A part of anything will be an identical part in the corresponding word in the process of individuation: The things and words will be partly entangled. The mapping of the things into the names will not be one-to-one yet. Those mixed states can be defined as "metaphors", and the class of all metaphors as "language as ontology". The problem of "meta-naming", i.e. the naming of "Reality" and "Representation" would arise. It can be resolved so: "Inelegantly": "Reality", i.e. that computer, where the first fluctuation does happen, doubles itself therefore creating a new "Paradise" and implying a "hierarchy of types" for the "bad infinite series" of doublings. "Representation" calls that somehow, and we call it "an elementary choice" or "a bit of information". "Elegantly": "Reality" creates a bit of information and "Representation" calls it somehow. The difference between the completeness of reality and the incompleteness of representation is only a bit of information. Nevertheless, there are too many ways for that bit to be deduced, seen, understood or interpreted. Language is definable also as the class of those ways, i.e. as the inelegant, but gradually extending description of the fundamental choice embodied in that bit. Electronic copy available at: https://ssrn.com/abstract=3638937 IV TURING MACHINES IN NASH EQUILIBRIUM A few early papers of Nash (1950; 1950a; 1951) prove a generalization (Park 2011) of Neumann's approach (Neumann, Morgenstern 1953: 238-290; Israel, Gasca 2009: 128-133; Nash et all 1996). The quotability of "Nash equilibrium" grows exponentially (Mccain, Mccain 2010). Nash obtained the Nobel Prize'1995 in economics. The Nash equilibrium can help to resolve the problem about how two or more Turing machines being independent of each other constitute a whole anyway. They should "play a game", which evolves into that equilibrium gradually. For example, two Turing machines should be initially in a "coherent state" coinciding therefore into a single one, which would decohere decreasing the degree of entanglement smoothly to two ones absolutely independent of each other. This would correspond to the mapping of a qubit into a bit, which is inadmissible according to the Kochen – Specker theorem (Kochen, Specker 1968: 70) and nevertheless necessary once the axiom of choice is postulated. The argument demonstrates how the Nash equilibrium and choice even in quantum mechanics rather than only in game theory are inherently linked to each other for the finiteness of a single Turing machine to be completed so that to represent a quantum Turing machine: The "second" Turing machine necessary for that can be interpreted as calculating the relative state of the first one according to the reference frame of a certain system comprising it. The independence of them embodied in the concept both of Nash equilibrium and choice corresponds to their complementarity in the sense of quantum mechanics. CONCLUSIONS AND FUTURE WORK Finiteness can be complemented to completeness in different ways explored in mathematics and quantum mechanics. One can utilize them for the formal definition of reality postulating it as what is complete unlike any representation of it. Then the fundamental relation of the completeness of reality and the incompleteness of any of its representations can serve for the formal and ontological definition of language. Turing machines in the Nash equilibrium can model practically that approach. Furthermore, a quantum computer defined as a quantum Turing machine can be decomposed to those Turing machines in the process of reaching the Nash equilibrium. Implementations in computer philosophy, science, and technics seem to be possible. Electronic copy available at: https://ssrn.com/abstract=3638937 REFERENCES: Aanderaa, S., P. Fischer (1967) "The Solvability of the Halting Problem for 2-State Post Machines," Journal of the ACM (JACM), 14(4): 677-682. Aspect, A., P. Grangier, and G. Roger (1981) Experimental Tests of Realistic Local Theories via Bell's Theorem. Physical Review Letters, 47 (7), 460-463. Aspect, A., P. Grangier, and G. Roger (1982) Experimental Realization of Einstein-Podolsky-RosenBohm Gedanken Experiment: A New Violation of Bell's Inequalities. Physical Review Letters, 49 (2), 9194. Basti, G. (2001) "Intentionality and Foundations of Logic: a New Approach to Neurocomputation," in: What should be computed to understand and model brain function?From robotics, soft computing, biology and neuroscience to cognitive philosophy (ed. T. Kitamura). Singapore; River Edge, NJ: World Scientific, 239288. Basti, G., A. L. Perrone (1889) "On the cognitive function of deterministic chaos in neural networks," in International Joint Conference on Neural Networks, vol. I. San Diego: IEEE, 657-663. Basti, G., A. L. Perrone (1995) "Chaotic neural nets, computability, and undecidability: Toward a computational dynamics," International Journal of Intelligent Systems, 10(1): 41-69. Bazhanov, V.A. (1993) "Pre-Godelian, Post-Godelian and non-Godelian Philosophy of Mathematics," in First International Symposium on Gödel's Theorem (Paris, May 27-29, 1991, ed. Z. Wolkowski), Singapore – New Jersey – London – Hong Kong: World Scientific, 51-60. Bell, J. (1964) On the Einstein ‒ Podolsky ‒ Rosen paradox. Physics (New York), 1 (3), 195-200. Benioff, P. (1980) "The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines," Journal of Statistical Physics, 22(5): 563-591. Benioff, P. (1998) "Models of Quantum Turing Machines," Fortschritte der Physik, 46(4-5): 423-441. Bloom, S. L. (1971) "Some Remarks on Uniform Halting Problems," Mathematical Logic Quarterly, 17(1): 281-284. Caporaso, S. (1978) "Consistency proof without transfinite induction for a formal system for Turing machines," Archiv für mathematische Logik und Grundlagenforschung, 19 (1): 157-164. Church, A. (1936) "A Note on the Entscheidungsproblem," The Journal of Symbolic Logic, 1(1): 40-41. Clauser, J. F. and M. A. Horne (1974) Experimental consequences of objective local theories. Physical Review D, 10(2): 526-535 Copeland, B. J. (2002) "Hypercomputation," Minds and Machines: Journal for Artificial Intelligence, Philosophy and Cognitive Science, 12(4): 461-502. Dedekind, R. (1888) Was sind und was sollen die Zahlen? Braunschweig :Friedrich Vieweg & Sohn. Deutsch, D. (1985) "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer," Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 400(1818): 97-117. Deutsch, D. (1989) "Quantum Computational Networks," Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 425(1868): 73-90. Deutsch, D., A. Ekert, and R. Lupacchini (2000) "Machines, Logic and Quantum Physics," Bulletin of Symbolic Logic, 6(3): 265-283. De Mol, E. (2006) "Closing the Circle: An Analysis of Emil Post's Early Work," Bulletin of Symbolic Logic 12 (2): 267 – 289. Dodig-Crnkovic, G. (2013) "Alan Turing's Legacy: Info-Computational Philosophy of Nature," in: Computing nature: Turing centenary perspective (eds. G. Dodig-Crnkovic and R. Giovagnoli). Berlin – New York: Springer, 115-123. Einstein, A., B. Podolsky, N. Rosen (1935) Can Quantum-Mechanical Description of Physical Reality Be Considered Complete? Physical Review, 47(10): 777-780. Feynman, R. P. (1996) Feynman lectures on computation. Reading, Mass.: Addison-Wesley. Fischer, P. C. (1969) "Quantificational variants on the halting problem for Turing machines," Mathematical Logic Quarterly, 15(13-15): 211-218. Electronic copy available at: https://ssrn.com/abstract=3638937 Friedman, H. M., and A. Sčedrov (1985) Arithmetic transfinite induction and recursive well-orderings. Advances in Mathematics, 56(3): 283-294. Foucault, M. (1966) Les mots et les choses; une archéologie des sciences humaines. Paris: Gallimard. (English translation: Foucault, M. (1994) The order of things: an archaeology of the human sciences. New York: Vintage Books.) Gaβner, C. (2008) "A Hierarchy below the Halting Problem for Additive Machines," Theory of Computing Systems, 43(3-4): 464-470. Gentzen, G. (1936) Die Widerspruchfreiheit der reinen Zahlentheorie. Mathematische Annalen, 112(1): 493-565. Gentzen, G. (1938) Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie. Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, New Series, 4(1): 19-44. Gentzen, G. (1943) Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion. Mathematische Annalen, 119(1): 140-161. Gentzen, G. (1954) Zusammenfassung von Mehreren Vollständigen Induktionen zu einer Einzigen. Archiv für mathematische Logik und Grundlagenforschung, 2(1): 1-3. Gerhard, G. (1974) Der erste Widerspruchsfreiheitsbeweis für die klassische Zahlentheorie. Archiv für mathematische Logik und Grundlagenforschung, 16(3-4): 97-118. Gentzen, G. (1974a) Über das Verhältnis zwischen intuitionistischer und klassischer Arithmetik. Archiv für mathematische Logik und Grundlagenforschung, 16(3-4): 119-132. Gödel, K. (1931) Über formal unentscheidbare Sätze der Principia mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38(1): 173-198. Gödel, K. [1938]. Lecture at Zilsel's. In: Collected Works (S. Feferman, J. W. Dawson, W. Goldfarb, C. Parsons, and R. M. Solovay: eds.) Vol. III. Oxford: Oxford University Press, 1995: 87-113. Gödel, K. (1958) Über eine bisher noch nicht benützte erweiterung des finiten standpunktes. Dialectica, 12(3-4): 280-287. Gunderson, D. S. (2011) Handbook of mathematical induction: theory and applications. Boca Raton, FL: CRC Press. Hamkins, J. D., D. E. Seabold (2001) "Infinite Time Turing Machines With Only One Tape," Mathematical Logic Quarterly, 47(2): 271-287. Hay, L. (1975) "Spectra and halting problems," Mathematical Logic Quarterly, 21(1): 167-176. Herman, G. T. (1968) "The Halting Problem of one State Turing Machines with n-Dimensional Tape," Mathematical Logic Quarterly, 14(7-12): 185-191. Herman, G. T. (1969) "The Unsolvability of the Uniform Halting Problem for Two State Turing Machines," The Journal of Symbolic Logic, 34( 2): 161-165. Herman, G. T. (1969a) "A Simple Solution of the Uniform Halting Problem," The Journal of Symbolic Logic, 34(4): 639-640. Herman, G. T. (1969b) "The uniform halting problem for generalized one-state turing machines," Information and Control, 15(4): 353-367. Herman, G. T. (1971) "Strong Computability and Variants of the Uniform Halting Problem," Mathematical Logic Quarterly, 17(1): 115-131. Hilbert, D. (1931) Die Grundlegung der elementaren Zahlenlehre. Mathematische Annalen , 104(1): 485494. Hilbert, D. und P. Bernays (1970) Grundlagen der Mathematik II (Zweite Auflage). Berlin Heidelberg New York: Springer. Hooper, P. K. (1966) "The Undecidability of the Turing Machine Immortality Problem," The Journal of Symholic Logic, 31(2): 219-234. Horská, A. (2014) Where is the Gödel-point hiding: Gentzen's consistency proof of 1936 and his representation of constructive ordinals. Heidelberg New York Dordrecht London: Springer. Howard, W. A. and G. Kreisel. (1966) Transfinite Induction and Bar Induction of Types Zero and One, and the Role of Continuity in Intuitionistic Analysis.The Journal of Symbolic Logic, 31(3): 325-358. Electronic copy available at: https://ssrn.com/abstract=3638937 Ikeda, K. and A. Tsuboi (2007) Nonstandard models that are definable in models of Peano Arithmetic. Mathematical Logic Quarterly, 53(1): 27-37. Israel, G., A. M. Gasca (2009) The world as a mathematical game: John von Neumann and twentieth century science. Basel: Birkhäuser. Jäger, G. (1993) Fixed points in Peano arithmetic with ordinals. Annals of Pure and Applied Logic, 60(2): 119-132. Kanckos, A. (2010) Consistency of Heyting arithmetic in natural deduction. Mathematical Logic Quarterly, 56(6): 611-624. Kleene, S. C. and R. E. Vesley (1965) The foundations of intuitionist mathematics, especially in relation to recursive functions. Amsterdam: North-Holland Publishing Company. Kochen, S. and E. Specker (1968) The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17 (1): 59-87. König, D. (1927) Über eine Schlussweise aus dem Endlichen ins Unendliche. Acta Scientarium mathematicarum (Szeged), 3(2-3): 121-130. Kreisel, G. (1958) Hilbert's programme. Dialectica, 12(3-4): 346-372 Kreisel, G. (1958a) Mathematical Significance of Consistency Proofs. Journal of Symbolic Logic, 23(2): 155-182. Lange, M. (2009) Why proofs by mathematical induction are generally not explanatory. Analysis, 69(2): 203-211. Lenzi, G., E. Monteleone (2004) "On Fixpoint Arithmetic and Infinite Time Turing Machines," Information Processing Letters, 91(3): 121-128. Maass, W. et al (1993) "Two tapes versus one for off-line Turing machines," Computational complexity, 3(4): 392-401. Margenstern, M. (1994) "Non-erasing Turing machines: a frontier between a decidable halting problem and universality," Theoretical Computer Science, 129(2): 419-424. Mahler, G., J. Gemmer, and M. Stollsteimer (2002) "Quantum computer as a thermodynamical machine," Superlattices and Microstructures, 31(2-3-4): 75-85. Manin Y. I. (2012) "Renormalisation and computation II: Time cut-off and the Halting Problem," Mathematical Structures in Computer Science, 22(5): 729-751. Mccain, K. W., R. A. Mccain (2010) "Influence & incorporation: John Forbes Nash and the "Nash Equilibrium"," Proceedings of the American Society for Information Science and Technology, 47(1): 1-2. Montagna, F. (1980) Interpretations of the first-order theory of diagonalizable algebras in peano arithmetic. Studia Logica, 39(4): 347-354. Murawski, R. (1999) Recursive functions and metamathematics: problems of completeness and decidability, Gödel's theorems. Dordrecht, Netherlands; Boston: Kluwer Academic. Neumann, J. von (1932) Mathematische Grundlagen der Quantenmechanik, Berlin: Julius Springer. Nash, J. F. (1950) "Equilibrium Points in n-Person Games," Proceedings of the National Academy of Sciences of the United States of America, 36(1): 48-49. Nash, J. (1950a) "The Bargaining Problem," Econometrica, 18(2): 155-162. Nash, J. et al (1996) "The work of John Nash in game theory," Journal of Economic Theory, 69(1): 153185. Nash, J. (1951) "Non-Cooperative Games," Annals of Mathematics, second Series, 54(2): 286-295. Neumann, J. Von, O. Morgenstern (1953) Theory of games and economic behavior. Princeton: University Press. Nishimura, H., M. Ozawa (2009) Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families," Quantum Information Processing, 8(1): 13-24. Palmgren, Erik; Sundholm, G. (eds). Epistemology versus Ontology. Dordrecht; New York: Springer, 87127. Park, S. (2011) "A history of the Nash equilibrium theorem in the fixed point theory," 数理解析研究所講 究録 / 京都大学数理解析研究所 [編], 1755(8): 76-89. Electronic copy available at: https://ssrn.com/abstract=3638937 Pavlotskaya, L. M. (2002) "Turing Machines Connected to the Undecidability of the Halting Problem," Mathematical Notes, 71(5): 667–675. Peano, I. (1889) Arithmetices principia: nova method exposita. Romae – Florentiae: Fratres Bocca. Pobedin, L. N. (1975) "The halt problem and theory of hierarchies," Algebra and Logic, 14(2): 112-123. Post, E. L. (1936) "Finite Combinatory Processes-Formulation 1," The Journal of Symbolic Logic, 1(3), 103-105. Priest, P. (1997) Yablo's paradox. Analysis, 57(4): 236-242. Rathjen, M. (2006) A note on Bar Induction in Constructive Set Theory. Mathematical Logic Quarterly, 52(3): 253 – 258. Resnik, M. D. (1974) On the philosophical significance of consistency proofs. Journal of Philosophical Logic, 3(1-2): 133-147. Royse, J. R. (1969). Mathematical induction in ramified type theory. Mathematical Logic Quarterly, 15(13): 7-10. Russell, B. (1902) Letter to Frege (16.06.1902). In: Gotlob Frege: Philosophical and mathematical correspondence (ed. G. Gabriel). Chicago: University of Chicago Press, 1980, 130-131. Sayama, H. (2008) "Construction theory, self-replication, and the halting problem," Complexity, 13(5): 16-22. Scarpellini, B. (1969) Some applications of Gentzens second consistency proof. Mathematische Annalen, 181(4): 325-344. Scarpellini, B. (1972) Induction and transfinite induction in intuitionistic systems. Annals of Mathematical Logic, 4(2): 173-227. Selman, A. L. (1974) "Relativized Halting Problems," Mathematical Logic Quarterly, 20(13-18): 193198. Shalyt-Margolin, A. E., V. I. Straznev, A. Y. Tregubovich (2007) "Irreversibility in the halting problem of quantum computer," Modern Physics Letters B, 21(16): 977-980. Siegelmann, H. T. (1996) "The simple dynamics of super Turing theories," Theoretical Computer Science, 168(2): 461-472. Schrödinger, E. (1935) Die gegenwärtige Situation in der Quantenmechanik. Naturwissenschaften, 23(48): 807-812; 23(49): 823-828; 23(50): 844-849. Sieg, W. (2012) In the Shadow of Incompleteness. Hilbert and Gentzen. In Dybjer, P.; Lindström, Sten; Skolem, T. [1922] Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre. In: Selected works in logic (J. E. Fenstad). Oslo: Universitetsforlaget, 1970, 137-152. Sommer, R. (1995). Transfinite induction within Peano arithmetic. Annals of pure and applied logic, 76(3): 231-289. Stannett, M. (1990) "X-machines and the halting problem: Building a super-Turing machine," Formal Aspects of Computing: Applicable Formal Methods, 2(1): 331-341. Stannett, M. (2006) "The case for hypercomputation," Applied Mathematics and Computation, 178(1): 824. Tait, W. W. (2005) Gödel's Reformulation of Gentzen's First Consistency Proof for Arithmetic: The NoCounterexample Interpretation. The Bulletin of Symbolic Logic, 11(2): 225-238. Tait, W. W. (2010) Gödel on Intuition and on Hilbert's finitism. In: Kurt Gödel: essays for his centennial (S. Feferman, C. Parsons, S. Simpson, eds.). New York: Cambridge University Press; Ithaca, NY: Association for Symbolic Logic, 88-108. Tanaka, Y. (2008) "On the computability of binary social choice rules in an infinite society and the halting problem," Applied Mathematics and Computation, 197(2): 598-603. Tazzioli, R. (2003) Towards a history of the geometric foundations of mathematics: Late XIXth century. Revue de Synthèse, 124(1): 11-41. Tennant, N. (2001) "On Turing Machines Knowing Their Own Gödel-Sentences," Philosophia Mathematica, 9(1): 72-79. Tlyusten, V. S. (1978) "Solvability of the uniform halting problem in the class of two-state post machines," Cybernetics, 14(1): 24-31. Electronic copy available at: https://ssrn.com/abstract=3638937 Towsner, H. (2005) Epsilon substitution for transfinite induction. Archive for Mathematical Logic, 44(4): 397-412. Turing, A. M. (1936) "On computable numbers: with an application to the Entscheidungsproblem," Proceedings of the London Mathematical Society. Ser. 2, 42(3-4), 230-265. Smorynski, C.A. (1973) Applications of Kripke models. In: Troelstra, A. S. (ed.) Metamathematical investigation of intuitionistic arithmetic and analysis. Berlin, Heidelberg, New York: Springer, 324-391. Visser, A. (1982) On the completenes principle: A study of provability in Heyting's arithmetic and extensions. Annals of Mathematical Logic, 22(3): 263-295. Welsh, P. D. (2009) "Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems" Theoretical Computer Science, 410(4-5): 426-442. Whitehead, N.A., and B. Russell (both editions) Principia mathematics. Vol. I. Cambridge: University Press. Yablo, S. (1993) Paradox without Self-Reference. Analysis, 53(4): 251-252. Yourgrau, P. (2006) A World Without Time: The Forgotten Legacy of Gödel and Einstein. New York: Perseus Books Group. Zach, R. (2003) The Practice of Finitism: Epsilon Calculus and Consistency Proofs in Hilbert's Program. Synthese, 137(1-2): 211-259. Electronic copy available at: https://ssrn.com/abstract=