-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Interview with Allyn Jackson scheduled for 5/28/20 1-2pm EDT * WHY? (NOT HISTORICAL PERSPECTIVE, BUT TECHNICAL PERSPECTIVE) TWO CATEGORIES: PHYSICAL -- LOGICAL/THEORETICAL STORAGE IS STANDARDIZED FOR NOISE IMMUNITY PROCESSSING IS STANDARDIZED (VALVE) / MAKES HIERARCHICAL ORGANIZATION NATURAL THE COOL VALVE CAN BE MADE VERY VERY SMALL! (QM!) LIMIT MOORE'S LAW (QM!) 1962 8 transistors on a chip / 1963 -- my dissertation -- 16 transistors MOORE, 1965 (64 transistors on a chip!) * DSP SOUND: NYQUIST CODING: DETECT & CORRECT ERRORS: SHANNON mid-1970s: TOM STOCKHAM / SOUNDSTREAM, 50 kHz. 16 bits NIXON TAPES, CARUSO RESTORATIONS ... MOORE'S LAW + PACKETS (DIGITAL!) + FIBER => INTERNET * COMPUTATION, THE MINIMAL "INTERESTING" COMPUTER, ENOUGH! TURING MACHINE=ANCHOR/FOUNDATION BUILD THEORETICAL CS ON IT, COMPLEXITY THEORY NAGGING QUESTION: CAN WE ALWAYS SIMULATE (EFFICIENTLY) THE REAL (ANALOG) WORLD? THESIS (NEVER A THEOREM): EXTENDED CHURCH-TURING THESIS (ECT) DEEP CONSEQUENCE: IF WE CAN SOLVE A "HARD PROBLEM" WITH ANALOG THEN WE CAN WITH TM! ECT + NP-COMPLETE ARE REALLY HARD => NO "MAGIC" HIDDEN IN THE ANALOG ANALOG/QM MAGIC IN THE BRAIN? * AI: WHAT ARE WE GOING TO GET? A HUMAN BRAIN? CAN IT FEEL? SUFFER? DOES IT HAVE RIGHTS? IS IT CONSCIOUS? ... SO MANY THREADS COME TOGETHER! I'VE BEEN THINKING ABOUT: WHAT NEXT? -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= WHY (not how) *Physical Reasons* NOISE of all sorts: thermal discreteness of nature: electrons, photons fundamentally unavoidable DIGITAL NOISE IMMUNITY depends on the principle of SIGNAL STANDARDIZATION => 0,1 VALVES ARE UNIVERSAL, from noise immunity (one kind of part is enough) QUANTUM MECHANICS sets the limitations on chip size and speed: PAULI EXCLUSION PRINCIPLE => transistors HEISENBERG'S UNCERTAINTY PRINCIPLE => resolution, integrated circuits *Logical Reasons* DSP: NYQUIST criterion INFORMATION THEORY & SHANNON'S NOISY CODING THEOREM *Computation & Problem Solving* ANALOG COMPUTERS: It seems that a mathematical difficulty in a problem (multiple solutions, no solution) inevitably and unavoidably manifests itself in a physical problem (getting stuck, multiple solutions.) Suggests a deep connection between mathematics and physics, and that the problem itself has some INTRINSIC DIFFICULTY. TURING MACHINES: Stored program (Jacquard) + conditional execution (Babbage) INTRINSIC DIFFICULTY of a problem POLYNOMIAL/EXPONENTIAL HIERARCHY; Turing equivalent; polynomially Turing equivalent. 2-SAT and 3-SAT; P, NP. A REDUCES to B (B is at least as hard as A). Define: X is NP-complete: Every problem in NP reduces to X. Implication: If X is NP-complete and we can solve it efficiently, then we can solve every problem in NP efficiently (it reduces to X). COOK'S THEOREM: 3-SAT is NP-complete. KARP: To show that a problem is NP-complete, reduce an NP-complete problem to it ARE ANALOG computers more POWERFUL than digital? attacks: soap films; PARTITION; Vergis missing law: Church-Turing; Extended Church-Turing locality and Bell's theorem; locally connected computer can't simulate QM QC is more powerful than classical, but apparently not that much more (?) *Internet, Robots* internet: 6 ideas: Signal standardization/valves/Moore's law/Nyquist/Shannon/Turing internet: packets not circuits / photons not electrons AI: neural nets; deep learning Is there analog magic in the brain? Quantum magic? What do learn from training a neural net? => Robots. Capek, Dick => Chalmers' "the hard problem of consciousness". Searle's strong AI, Chinese room argument against it. Values. -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= The Discrete Charm of the Machine: Why the World Became Digital Ken Steiglitz 1. What is the aim of the book? The subtitle: To explain why the world became digital. Barely two generations ago our information machines---radio, TV, computers, telephones, phonographs, cameras---were analog. Information was represented by smoothly varying waves. Today all these devices are digital. Information is represented by bits, zeros and ones. We trace the reasons for this radical change, some based on fundamental physical principles, others on ideas from communication theory and computer science. At the end we arrive at the present age of the internet, dominated by digital communication, and finally greet the arrival of androids---the logical end of our current pursuit of artificial intelligence. 2. What role did war play in this transformation? Sadly, World War II was a major impetus to many of the developments leading to the digital world, mainly because of the need for better methods for decrypting intercepted secret messages and more powerful computation for building the atomic bomb. The following cold war just increased the pressure. Business applications of computers and then, of course, the personal computer opened the floodgates for the machines that are today never far from our fingertips. 3. How did you come to study this subject? I lived it. As an electrical engineering undergraduate I used both analog and digital computers. My first summer job was programming one of the few digital computers in Manhattan at the time, the IBM 704. In graduate school I wrote my dissertation on the relationship between analog and digital signal processing and my research for the next twenty years or so concentrated on digital signal processing: using computers to process sound and images in digital form. 4. What physical theory played---and continues to play---a key role in the revolution? Quantum mechanics, without a doubt. The theory explains the essential nature of noise, which is the natural enemy of analog information; it makes possible the shrinkage and speedup of our electronics (Moore's law); and it introduces the possibility of an entirely new kind of computer, the quantum computer, which can transcend the power of today's conventional machines. Quantum mechanics shows that many aspects of the world are essentially discrete in nature, and the change from the classical physics of the nineteenth century to the quantum mechanics of the twentieth is mirrored in the development of our digital information machines. 5. What mathematical theory plays a key role in understanding the limitations of computers? Complexity theory and the idea of an intractable problem, as developed by computer scientists. This theme is explored in part III, first in terms of analog computers, then using Alan Turing's abstraction of digital computation, which we now call the Turing machine. This leads to the formulation of the most important open question of computer science, does P equal NP? If P equals NP it would mean that any problem where solutions can just be checked fast can be solved fast. This seems like asking a lot, and, in fact, most computer scientists believe that P does not equal NP. Problems as hard as any in NP are called NP-complete. The point is that NP-complete problems, like the famous traveling salesman problem, seem to be intrinsically difficult, and cracking any one of them cracks them all. Their essential difficulty manifests itself, mysteriously, in many different ways in the analog and digital worlds, suggesting, perhaps, that there is an underlying physical law at work. 6. What important open question about physics (not mathematics) speaks to the relative power of digital and analog computers? The extended Church-Turing thesis states that any reasonable computer can be simulated efficiently by a Turing machine. Informally, it means that no computer, even if analog, is more powerful (in an appropriately defined way) than the bare-boned, step-by-step, one-tape Turing machine. The question is open, but many computer scientists believe it to be true. This line of reasoning leads to an important conclusion: if the extended Church-Turing thesis is true, and if P is not equal to NP (which is widely believed), then the digital computer is all we need---Nature is not hiding any computational magic in the analog world. 7. What does all this have to do with artificial intelligence (AI)? The brain uses information in both analog and digital form, and some have even suggested that it uses quantum computing. So, the argument goes, perhaps the brain has some special powers that cannot be captured by ordinary computers. 8. What does philosopher David Chalmers call the hard problem? We finally reach---in the last chapter---the question of whether the androids we are building will ultimately be conscious. Chalmers calls this the hard problem, and some, including myself, think it unanswerable. An affirmative answer would have real and important consequences, despite the seemingly esoteric nature of the question. If machines can be conscious, and presumably also capable of suffering, then we have a moral responsibility to protect them, and---to put it in human terms---bring them up right. I propose that we must give the coming androids the benefit of the doubt; we owe them the same loving care that we as parents bestow on our biological offspring. 9. Where do we go from here? A funny thing happens on the way from chapter 1 to 12. I begin with the modest plan of describing, in the simplest way I can, the ideas behind the analog-to-digital revolution. We visit along the way some surprising tourist spots: the Antikythera mechanism, a 2000-year old analog computer built by the ancient Greeks; Jacquard's embroidery machine with its breakthrough stored program; Ada Lovelace's program for Babbage's hypothetical computer, predating Alan Turing by a century; and B. F. Skinner's pigeons trained in the manner of AI to be living smart bombs. We arrive at a collection of deep conjectures about the way the universe works and some challenging moral questions.