Computation

Computation#

Table of Contents#

Figures#

  • [ w ][ s ] 0780-0850 Al-Khwarismi

  • [ w ][ s ] 1791-1871 Babbage, Charles

  • [ w ][ s ] 1924-2007 Backus, John

  • [ w ][ s ] 1685-1753 Berkeley, George

  • [ w ][ s ] 1815-1864 Boole, George

  • [ w ][ s ] 1973----- Bostrom, Nick

  • [ w ][ s ] 1915-2008 Burks, Arthur

  • [ w ][ s ] 1890-1974 Bush, Vannevar

  • [ w ][ s ] 1966----- Chalmers, David

  • [ w ][ s ] 1928----- Chomsky, Noam

  • [ w ][ s ] 1937-2020 Conway, John

  • [ w ][ s ] 1950----- Copeland, Jack

  • [ w ][ s ] 1903-1995 Church, Alonzo

  • [ w ][ s ] 1942----- Dennett, Daniel

    • [ w ] 2017 From Bacteria to Bach and Back: The Evolution of Minds

  • [ w ][ s ] 1596-1650 Descartes, Rene

  • [ w ][ s ] 1930-2002 Dijkstra, Edsger

  • [ w ][ s ] 1914-2010 Gardner, Martin

  • [ w ][ s ] 1906-1978 Gödel, Kurt

  • [ w ][ s ] 1955----- Hoffman, Donald

  • [ w ][ s ] 1939----- Hopcroft, John

    • [ w ] Cinderella Book

  • [ w ][ s ] 1724-1904 Kant, Immanuel

  • [ w ][ s ] 1938----- Knuth, Donald

    • [ w ] The Art of Computer Programming

  • [ w ][ s ] 1646-1716 Leibniz, Gottfried

  • [ w ][ s ] 1815-1852 Lovelace, Ada

  • [ w ][ s ] 1947----- Mainzer, Klaus

  • [ w ][ s ] 1623-1662 Pascal, Blaise

  • [ w ][ s ] 1931----- Penrose, Roger

  • [ w ][ s ] 1897-1954 Post, Emil

  • [ w ][ s ] 1932----- Searle, John

  • [ w ][ s ] 1912-1954 Turing, Alan

  • [ w ][ s ] 1942----- Ullman, Jeffrey

  • [ w ][ s ] 1903-1957 Von Neumann, John

  • [ w ][ s ] 1959----- Wolfram, Stephen

  • [ w ][ s ] 1910-1995 Zuse, Konrad

[ w ] pioneers in computer science

Resources#

[ y ] MIT 18.404J Theory of Computation, Fall 2020

  • [ y ] 10-06-2021. “1. Introduction, Finite Automata, Regular Expressions”.

  • [ y ] 10-06-2021. “2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA”.

  • [ y ] 10-06-2021. “3. Regular Pumping Lemma, Conversion of FA to Regular Expressions”.

  • [ y ] 10-06-2021. “4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion”.

  • [ y ] 10-06-2021. “5. CF Pumping Lemma, Turing Machines”.

  • [ y ] 10-06-2021. “6. TM Variants, Church-Turing Thesis”.

  • [ y ] 10-06-2021. “7. Decision Problems for Automata and Grammars”.

  • [ y ] 10-06-2021. “8. Undecidability”.

  • [ y ] 10-06-2021. “9. Reducibility”.

  • [ y ] 10-06-2021. “10. Computation History Method”.

  • [ y ] 10-06-2021. “11. Recursion Theorem and Logic”.

  • [ y ] 10-06-2021. “12. Time Complexity”.

  • [ y ] 10-06-2021. “14. P and NP, SAT, Poly-Time Reducibility”.

  • [ y ] 10-06-2021. “15. NP-Completeness”.

  • [ y ] 10-06-2021. “16. Cook-Levin Theorem”.

  • [ y ] 10-06-2021. “17. Space Complexity, PSPACE, Savitch’s Theorem”.

  • [ y ] 10-06-2021. “18. PSPACE-Completeness”.

  • [ y ] 10-06-2021. “19. Games, Generalized Geography”.

  • [ y ] 10-06-2021. “20. L and NL, NL = coNL”.

  • [ y ] 10-06-2021. “21. Hierarchy Theorems”.

  • [ y ] 10-06-2021. “22. Provably Intractable Problems, Oracles”.

  • [ y ] 10-06-2021. “23. Probabilistic Computation, BPP”.

  • [ y ] 10-06-2021. “24. Probabilistic Computation (cont.)”.

  • [ y ] 10-06-2021. “25. Interactive Proof Systems, IP”.

  • [ y ] 10-06-2021. “26. coNP is a subset of IP”.

  • [ y ] 01-07-2016. Science University of Copenhagen. “Reversible Computing”.

  • [ y ] 03-31-2024. William Byrd. “Reversible Computing, Part 2”.

  • [ y ] 02-19-2024. William Byrd. “Reversible Computing, Part 1”.

[ y ] Easy Theory’s Context-Free Grammars (CFGs)

  • [ y ] 07-19-2021. “Pumping Lemma for Regular Languages TWENTY Examples and Proof Strategies!”.

  • [ y ] 11-11-2020. “Regular Languages in 4 Hours (DFA, NFA, Regex, Pumping Lemma, all conversions)”.

Nerd’s Lesson

  • [ y ] 02-27-2022. “Theory of Computation and Automata Theory ( Full Course )”.

P vs NP

  • [ y ] 05-16-2016. Institute for Advanced Study. “The “P vs. NP” Problem: Efficient Computation….Knowledge” - Avi Wigderson”.

  • [ y ] 01-04-2020. Lex Fridman. “Donald Knuth: P=NP | AI Podcast Clips”.

  • [ y ] 12-01-2023. Quanta Magazine. “P vs. NP: The Biggest Puzzle in Computer Science”.

More

  • [ y ] 10-05-2020. Alan Zucconi. “Let’s BUILD a COMPUTER in CONWAY’s GAME of LIFE ⠠⠵”.

  • [ y ] 10-09-2023. Freethink. “Analog computing will take over 30 billion devices by 2040. Wtf does that mean? | Hard Reset”.

  • [ y ] 11-05-2023. Projections. “OPTICAL COMPUTING with PLASMA: Stanford PhD Defense”.

  • [ y ] 2012. Talks at Google. “Think Complexity | Allen B. Downey | Talks at Google”.

Online

  • teach yourself computer science

  • [ h ][ y ] The Simons Institute for the Theory of Computing

  • [ p ] “Time Complexity: Why Some Algorithms Run for Billions of Years”.

  • [ p ] Khan Academy’s Intro to Algorithms

Texts#

  • Bernhardt, Chris. (2017). Turing’s Vision: The Birth of Computer Science. MIT Press.

  • [ w ] Copeland, Jack et al. The Turing Guide. Oxford University Press.

  • [ h ][ g ] Downey, Allen B. (2018). Think Complexity: Complexity Science and Computational Modeling. 2nd Ed. O’Reilly.

  • [ h ] Esparza, Javier & Michael Blondin. (2023). Automata Theory: An Algorithmic Approach. MIT Press.

  • Feynman, Richard P. (1996). Feynman Lectures on Computation. CRC Press.

  • [ h ][ g ] Hefferon, Jim. Theory of Computation: Making Connections.

  • [ h ] MacCormick, John. (2018). What Can Be Computed?: A Practical Guide to the Theory of Computation. Princeton University Press.

  • Mainzer, Klaus. (2017). The Digital and the Real World: Computational Foundations of Mathematics, Science, Technology, and Philosophy. World Scientific.

  • Mainzer, Klaus & Leon Chua. (2012). The Universe as Automaton: From Simplicity and Symmetry to Complexity. Springer Briefs in Complexity.

  • Mainzer, Klaus. (2007). Thinking in Complexity: The Computational Dynamics of Matter, Mind, and Mankind. Springer.

  • [ h ] Moore, Christopher. (2011). The Nature of Computation. Oxford University Press.

  • [ w ] Penrose, Roger. (1989). The Emperor’s New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford University Press.

  • [ h ][ g ] Russell, Stuart & Peter Norvig. (2020). Artificial Intelligence: A Modern Appraoch. 4th Ed. Pearson.

  • [ h ] Savage, John E. (1998). Models of Computation: Exploring the Power of Computing. Addison-Wesley.

  • Stuart, Tom. (2013). Understanding Computation: From Simple Mechanics to Impossible Programs. O’Reilly.

  • Von Neumann, John. (1966). Theory of Self-Reproducing Automata. Arthur Burks (ed.). University of Illinois Press.

[ w ] a list of noteworthy publications in computer science

Terms#

  • [ w ][ sep ] 256 Rules

  • [ w ] Algorithm

  • [ w ] Algorithmic Learning Theory

  • [ w ] Analytical Engine

  • [ w ] Animism

  • [ w ] Artificial Consciousness

  • [ w ] AG Artificial General Intelligence

  • [ w ] AI Artificial Intelligence

  • [ w ] Artificial Life

  • [ w ] Automata Theory

  • [ w ] Automaton

  • [ w ] BlooP and FlooP

  • [ w ] Boolean Circuit

  • [ w ] Boolean Function

  • [ w ] Cantor’s Diagonal Argument

  • [ w ][ sep ] Cellular Automaton

  • [ w ] Chinese Room

  • [ w ][ sep ] Church-Turing Thesis

  • [ w ] Circuit

  • [ w ] Circuit Complexity

  • [ w ] Cognition

  • [ w ] Combinational Logic

  • [ w ] Complex System

  • [ w ][ sep ] Computability and Complexity

  • [ w ] Computability Theory

  • [ w ][ sep ] Computational Complexity Theory

  • [ w ] Computational Learning Theory

  • [ w ] Computer Algebra

  • [ w ] Consciousness

  • [ w ] Conway’s Game of Life

  • [ w ] Decider

  • [ w ] Decision Problem

  • [ w ] Difference Engine

  • [ w ] Electromechanics

  • [ w ][ sep ] Embodied Cognition

  • [ w ] Emergentism

  • [ w ] FSA Finite-State Automaton

  • [ w ] FSM Finite-State Machine

  • [ w ] Greenberg-Hastings Cellular Automaton

  • [ w ] Halting Problem

  • [ w ] Hard Problem of Consciousness

  • [ w ][ sep ] Idealism

  • [ w ] Introspection

  • [ w ] Jacquard Machine

  • [ w ] Knowledge Representation and Reasoning

  • [ w ] Lambda Calculus

  • [ w ] Machine Learning

  • [ w ] Mechanical Calculator

  • [ w ] Mechanical Computer

  • [ w ] Mental Representation

  • [ w ] Metacognition

  • [ w ] Mind

  • [ w ] Mind-Body Dualism

  • [ w ] Mind-Body Problem

  • [ w ] Model of Computation

  • [ w ] Noumenon

  • [ w ] NP Completeness

  • [ w ] Panpsychism

  • [ w ] Perception

  • [ w ] Phenomenology

  • [ w ] Phenomenon

  • [ w ] Philosophy of Artificial Intelligence

  • [ w ][ sep ] Philosophy of Computer Science

  • [ w ] Philosophy of Mind

  • [ w ][ sep ] Philosophy of Technology

  • [ w ] Pushdown Automaton

  • [ w ] Qualia

  • [ w ] Quine

  • [ w ] Recursion Theory

  • [ w ] Reductionism

  • [ w ] Recursive Language

  • [ w ] Richardson’s Theorem

  • [ w ] Sapience

  • [ w ] Sentience

  • [ w ] Sequential Logic

  • [ w ] Space Complexity

  • [ w ] Stack Machine

  • [ w ] State

  • [ w ] State Machine

  • [ w ] Statistical Learning Theory

  • [ w ] Stream of Consciousness

  • [ w ] Superintelligence

  • [ w ] Tessellation

  • [ w ] Theoretical Computer Science

  • [ w ] Theory of Computation

  • [ w ] Thing-in-itself

  • [ w ] Total TM Turing Machine

  • [ w ] Turing Completeness

  • [ w ][ sep ] Turing Machine

  • [ w ] Turing Test

  • [ w ] Undecidable Problem

  • [ w ] Universal Turing Machine

  • [ w ] Von Neumann Universal Constructor

  • [ w ] Weak AI

Notes#

Quotes#

Edsger Dijkstra

  • “The question of whether Machines Can Think…is about as relevant as the question of whether Submarines Can Swim.” The threats to computing science (1984)

Bernardo Kastrup

  • “A computer is a silicon device…that does not metabolize, it’s something completely different. So it’s entirely arbitrary to project our own conscious inner life on a computer. It does not have any tenable empirical basis. Can I with certainty discard that hypothesis that a computer can become conscious in and of itself? I cannot. But I cannot with certainty discard the hypothesis that there is a teapot in the orbit of Saturn. I cannot discard with certainty the hypothesis of the flying spaghetti monster. There are a great many things that are nonsensical and that I cannot with certainty refute. That’s not the important question. The important question is what do we have reasons to belive. Do we have reasons to believe that a silicon computer is conscious in and of itself? I would say none. Computers simulate consciousness. But you see, I can simulate kidney function on my computer right now accurately down to the molecular level. That doesn’t mean my computer will pee on my desk because a simulation is not the thing simulated. So when people say if I simulate human intelligence in a computer then the computer is conscious, what you are saying is that if you simulate kidney function then the computer will pee on your desk. It’s just…arbitrary and frankly absurd.” Russell Brand. (July 26, 2022). “Hang On, Could AI Do THIS?!”. YouTube.

Contents