S
smeyer0028
Guest
John von Neumann in the 1950s already considered abstract models of computers in designing the von Neumann architecture that is used to build modern computers. The problem is that although Turing Machines are universal, they are slow because they lack random access and bit accessing "instructions." Here is an abstract along with references submitted to the British Society for the Philosophy of Science (BSPS) conference that describes von Nuemann's use of the MRAM model in designing modern computers. There is no class NP (problems that require guessing) in the MRAM model because computers can enumerate as fast (in the polynomial bounded sense) as Turing Machines can guess.
===========
John von Neumann's Natural Philosophy of Computing
John von Neumann's transformation from a mathematician in the 1920s to a natural philosopher in the 1950s is best expressed by a story Neumann told expressing Wolfgang Pauli's criticism of formal
mathematics. 'If a mathematical proof is what matters in physics, you would be a great physicist.' (Thirring[2001], p. 5). Neumann's transitioned from adherent of David Hilbert's programme that all knowledge could be axiomatized in the 1920s to a natural philosopher of computation in the 1950s. Kurt Godel's incompleteness results in the late 1920s and discussions with physicists in the 1930s were some factors that may have motivated Neumann's change. For example, in an exchange with Niels Bohr at the 1936 Warsaw New Theories in Physics Conference (IntCoop[1936]), Neumann agreed with Bohr that his Hilbert Space formalization is problematic.
Starting in the early 1940s, Neumann became focused on the possibilities of digital computers (See Aspray[1990] for a detailed history). Neumann did not explicitly discuss his philosophy of computation, but he did discuss his thinking about abstract properties that a computer architecture should have. He seems not to have considered Turing Machines (TM) at all because he had already rejected the Hilbert programme. His explicit rejection of formal neural networks also sheds light on his computational philosophy (Aspray[1990], note 94, p. 321).This paper provides an over view of Neumann's thinking by discussing a modern formalization of computation using an abstract model called MRAMs (random access machines with unbounded cell size and unit multiply) first studied by Hartmanis and Simon (Hartmanis[1974][1974a]). Neumann explicitly listed the requirements for his now almost universally used von Neumann computer architecture that match the properties of the MRAM model. In contrast to TMs that have an unbounded number of bounded size memory cells, Neumann assumed that a computer would have a finite number of unbounded (in the 19th century sense of infinity) size memory cells. Neumann also argued that some sort of intuition needed to be built into programs instead of brute force searching (Aspray[1990], p. 62). MRAM model allows random access table look up data structures (see Meyer[2016] for more details on Neumann's thinking).
There are modern consequences of Neumann's philosophy. In the MRAM model the P?=NP problem does not exist (or the answer is that there is no difference between the class of problems solvable by non deterministic guessing versus the class solvable by deterministic searching). Many modern philosophical questions assume implicitly that non deterministic TMs are more powerful than deterministic machines. For example, Shor's quantum computation algorithms assume the P?=NP problem (Shor[1997]). Scientists are seemingly building physical devices based on the rejected assumptions of the Hilbert programme.
An interesting story related to Neumann's philosophy is that advocates of the importance of the P?=NP problem (does guessing speed up computation by more than a polynomial bound) found a letter in the Godel Archive to Neumann that they interpret as Godel supporting the importance of the P?=NP problem. However, in a letter written probably in the 1940s by Neumann to Oswald Veblen relating to an Institute of Advanced Study appointment, Neumann shows skepticism toward Godel's later work (Hartmanis[1989] for the Godel P?=NP letter, Neumann[2005], p. 276 for the Neumann letter).
To me the most important consequence of Neumann's natural philosophy and computer architecture is that TMs are really very weak (slow) computing machines. It is true that TMs are universal in the Church Turing sense (Copeland[2015]). Any TM can calculate anything recursively computable in the Church Turing sense (for background the question 'are two regular expressions equivalent' is outside NP but computable). The thesis is often expressed as any TM can simulate any computing device. The problem is that modern thinking views computational efficiency as important. In that sense, TMs are slow. Another way of viewing the important of MRAMs and Neumann's philosophy is that they falsify (in the Popperian sense) the Church Turing thesis.
References:
Aspray[1990]
Aspray, W. John von Neumann and The Origins of Modern
Computing. MIT Press, 1990.
Copeland[2015]
Copeland, J. The Church-Turing thesis. The Stanford Encyclopedia
of Philosophy (Summer 2015 Edition), 2015. URL Feb. 2018:
plato.stanford.edu/archives/sum2015/entries/church-turing
Hartmanis[1974]
Hartmanis, J. and Simon, J. On the Structure of Feasible
Computations. Lecture Notes in Computer Science, Vol. 26. Also
Cornell Ecommons URL Jan. 2016:
On the Structure of Feasible Computations, 1974, 1-49.
Hartmanis[1974a]
Hartmanis, J. and Simon, J. The Power of Multiplication In
Random Access Machines. 15th IEEE Conference on Switching
and Automata. IEEE, Oct. 1974, 13-23.
Hartmanis[1989]
Hartmanis, J. Godel, von Neumann and the P=?NP Problem.
Periodic Structural Complexity Column. April 1989. Cornell
Ecommons URL Jan. 2016: eCommons - Cornell digital repository
Godel, von Neumann and the P=?NP Problem
IntCoop[1938]
International Institute of Intellectual Co-operation, New Theories
in Physics, conference proceedings, Warsaw, 1938.
Meyer[2016]
Meyer, S. Philosophical Solution to P=?NP: P is equal to NP,
ArXiv:1603:06018, 2016.
Neumann[2005]
Von Neumann, J. (Redei, M. ed.) John Von Neumann: Selected Letters.
History of Mathematics Series, Vol. 27, American Mathematical Society, 2005.
Shor[1997]
Shor, P. Polynomial-Time Algorithms for Prime Factorization and
Discrete Logarithms on a Quantum Computer. arXiv:quant-ph/9508027v2.
Thirring[2001]
Thirring, W. J. v. Neumann’s Influence in Mathematical Physics.
In Redei, M. and Stoltzner, M. (eds.) John von Neumann and the
Foundations of Quantum Physics. Vienna Circle Institute
Yearbook 8, Kluwer, 2001, 5-10.
===========
John von Neumann's Natural Philosophy of Computing
John von Neumann's transformation from a mathematician in the 1920s to a natural philosopher in the 1950s is best expressed by a story Neumann told expressing Wolfgang Pauli's criticism of formal
mathematics. 'If a mathematical proof is what matters in physics, you would be a great physicist.' (Thirring[2001], p. 5). Neumann's transitioned from adherent of David Hilbert's programme that all knowledge could be axiomatized in the 1920s to a natural philosopher of computation in the 1950s. Kurt Godel's incompleteness results in the late 1920s and discussions with physicists in the 1930s were some factors that may have motivated Neumann's change. For example, in an exchange with Niels Bohr at the 1936 Warsaw New Theories in Physics Conference (IntCoop[1936]), Neumann agreed with Bohr that his Hilbert Space formalization is problematic.
Starting in the early 1940s, Neumann became focused on the possibilities of digital computers (See Aspray[1990] for a detailed history). Neumann did not explicitly discuss his philosophy of computation, but he did discuss his thinking about abstract properties that a computer architecture should have. He seems not to have considered Turing Machines (TM) at all because he had already rejected the Hilbert programme. His explicit rejection of formal neural networks also sheds light on his computational philosophy (Aspray[1990], note 94, p. 321).This paper provides an over view of Neumann's thinking by discussing a modern formalization of computation using an abstract model called MRAMs (random access machines with unbounded cell size and unit multiply) first studied by Hartmanis and Simon (Hartmanis[1974][1974a]). Neumann explicitly listed the requirements for his now almost universally used von Neumann computer architecture that match the properties of the MRAM model. In contrast to TMs that have an unbounded number of bounded size memory cells, Neumann assumed that a computer would have a finite number of unbounded (in the 19th century sense of infinity) size memory cells. Neumann also argued that some sort of intuition needed to be built into programs instead of brute force searching (Aspray[1990], p. 62). MRAM model allows random access table look up data structures (see Meyer[2016] for more details on Neumann's thinking).
There are modern consequences of Neumann's philosophy. In the MRAM model the P?=NP problem does not exist (or the answer is that there is no difference between the class of problems solvable by non deterministic guessing versus the class solvable by deterministic searching). Many modern philosophical questions assume implicitly that non deterministic TMs are more powerful than deterministic machines. For example, Shor's quantum computation algorithms assume the P?=NP problem (Shor[1997]). Scientists are seemingly building physical devices based on the rejected assumptions of the Hilbert programme.
An interesting story related to Neumann's philosophy is that advocates of the importance of the P?=NP problem (does guessing speed up computation by more than a polynomial bound) found a letter in the Godel Archive to Neumann that they interpret as Godel supporting the importance of the P?=NP problem. However, in a letter written probably in the 1940s by Neumann to Oswald Veblen relating to an Institute of Advanced Study appointment, Neumann shows skepticism toward Godel's later work (Hartmanis[1989] for the Godel P?=NP letter, Neumann[2005], p. 276 for the Neumann letter).
To me the most important consequence of Neumann's natural philosophy and computer architecture is that TMs are really very weak (slow) computing machines. It is true that TMs are universal in the Church Turing sense (Copeland[2015]). Any TM can calculate anything recursively computable in the Church Turing sense (for background the question 'are two regular expressions equivalent' is outside NP but computable). The thesis is often expressed as any TM can simulate any computing device. The problem is that modern thinking views computational efficiency as important. In that sense, TMs are slow. Another way of viewing the important of MRAMs and Neumann's philosophy is that they falsify (in the Popperian sense) the Church Turing thesis.
References:
Aspray[1990]
Aspray, W. John von Neumann and The Origins of Modern
Computing. MIT Press, 1990.
Copeland[2015]
Copeland, J. The Church-Turing thesis. The Stanford Encyclopedia
of Philosophy (Summer 2015 Edition), 2015. URL Feb. 2018:
plato.stanford.edu/archives/sum2015/entries/church-turing
Hartmanis[1974]
Hartmanis, J. and Simon, J. On the Structure of Feasible
Computations. Lecture Notes in Computer Science, Vol. 26. Also
Cornell Ecommons URL Jan. 2016:
On the Structure of Feasible Computations, 1974, 1-49.
Hartmanis[1974a]
Hartmanis, J. and Simon, J. The Power of Multiplication In
Random Access Machines. 15th IEEE Conference on Switching
and Automata. IEEE, Oct. 1974, 13-23.
Hartmanis[1989]
Hartmanis, J. Godel, von Neumann and the P=?NP Problem.
Periodic Structural Complexity Column. April 1989. Cornell
Ecommons URL Jan. 2016: eCommons - Cornell digital repository
Godel, von Neumann and the P=?NP Problem
IntCoop[1938]
International Institute of Intellectual Co-operation, New Theories
in Physics, conference proceedings, Warsaw, 1938.
Meyer[2016]
Meyer, S. Philosophical Solution to P=?NP: P is equal to NP,
ArXiv:1603:06018, 2016.
Neumann[2005]
Von Neumann, J. (Redei, M. ed.) John Von Neumann: Selected Letters.
History of Mathematics Series, Vol. 27, American Mathematical Society, 2005.
Shor[1997]
Shor, P. Polynomial-Time Algorithms for Prime Factorization and
Discrete Logarithms on a Quantum Computer. arXiv:quant-ph/9508027v2.
Thirring[2001]
Thirring, W. J. v. Neumann’s Influence in Mathematical Physics.
In Redei, M. and Stoltzner, M. (eds.) John von Neumann and the
Foundations of Quantum Physics. Vienna Circle Institute
Yearbook 8, Kluwer, 2001, 5-10.
Last edited by a moderator: