CT3620 VETENSKAPSMETODIK FÖR TEKNIKOMRÅDET HISTORY OF IDEAS IN COMPUTING Gordana Dodig-Crnkovic Department of Computer Science and Engineering Mälardalen University 2004 1 CDT403 Research Methodology in Natural Sciences and Engineering A History of Computing: A History of Ideas Gordana Dodig-Crnkovic Department of Computer Science and Electronic Mälardalen University, Sweden 2 HISTORY OF COMPUTING • • • • • • • • • • LEIBNIZ: LOGICAL CALCULUS BOOLE: LOGIC AS ALGEBRA FREGE: MATEMATICS AS LOGIC CANTOR: INFINITY HILBERT: PROGRAM FOR MATHEMATICS GÖDEL: END OF HILBERTS PROGRAM TURING: UNIVERSAL AUTOMATON VON NEUMAN: COMPUTER CONCEPT OF COMPUTING FUTURE COMPUTING 3 4 Pieter BRUEGEL, the Elder COMPUTING CURRICULA 5 Technological Advancement within Computing over the Past Decade – The World Wide Web and its applications – Networking technologies, particularly those based on TCP/IP – Graphics and multimedia – Embedded systems – Relational databases – Interoperability – Object-oriented programming – The use of sophisticated application programmer interfaces (APIs) – Human-computer interaction – Software safety – Security and cryptography – … 6 Hackers & Painters "Everything around us is turning into computers. Your typewriter is gone, replaced by a computer. Your phone has turned into one. So has your camera. Soon your TV will. Your car has more processing power in it than a roomsized mainframe had in 1970. Letters, encyclopedias, newspapers, and even your local store are being replaced by the Internet. So if you want to understand where we are, and where we're going, it will help if you understand what's going on inside the heads of hackers.“ Paul Graham "Hackers & Painters" 7 Hackers & Painters Hacking and painting have a lot in common. In fact, of all the different types of people I’ve known, hackers and painters are among the most alike. Paul Graham "Hackers & Painters" 8 Yet there is a whole universe of people contributing to the development of the field of computing rather different from hackers and painters... 9 Computer Science In practice, computer science includes a variety of topics relating to computers, which range from the abstract analysis of algorithms, formal grammars, etc. to more concrete subjects like programming languages, software, and computer hardware. As a scientific discipline, it differs significantly from and is often confused with mathematics, programming, software engineering, and computer engineering, although there is some degree of overlap with these and other fields. http://en.wikipedia.org/wiki/Computer_science 10 Church-Turing Thesis The Church-Turing thesis states that all known kinds of reasonable paradigms of computation are essentially equivalent in what they can do, although they vary in time and space efficiency. The thesis is not a mathematical theorem that can be proven, but an empirical observation that all known computational schemes have the same computational power. Now the problem is what is the ”reasonable paradigm of computation” – we will have reason to come back to this point later on in this lecture. 11 Computer Most research in computer science has been related to von Neumann computers or Turing machines (computers that do one small, deterministic task at a time). These models resemble most real computers in use today. Computer scientists also study other kinds of machines, some practical (like parallel machines) and some theoretical (like probabilistic, oracle, and quantum machines). 12 Computer Science Computer scientists study what programs can and cannot do (computability), how programs should efficiently perform specific tasks (algorithms), how programs should store and retrieve specific kinds of information (data structures and data bases), how programs might behave intelligently (artificial intelligence), and how programs and people should communicate with each other (human-computer interaction and user interfaces). 13 CS Body of Knowledge – – – – – – – – – – – – – – – Discrete Structures Programming Fundamentals Algorithms and Complexity Programming Languages Architecture and Organization Operating Systems Net-Centric Computing Human-Computer Interaction Graphics and Visual Computing Intelligent Systems Information Management Software Engineering Social and Professional Issues Computational Science and Numerical Methods ... 14 Related Fields Computer science is closely related to a number of fields. These fields overlap considerably, though important differences exist • Information science is the study of data and information, including how to interpret, analyze, store, and retrieve it. Information science started as the foundation of scientific analysis of communication and databases. • Computer programming or software development is the act of writing program code. 15 Related Fields • Software engineering emphasizes analysis, design, construction, and testing of useful software. Software engineering includes development methodologies (such as the waterfall model and extreme programming) and project management. • Information systems (IS) is the application of computing to support the operations of an organization: operating, installing, and maintaining the computers, software, and data. • Computer engineering is the analysis, design, and construction of computer hardware 16 Related Fields • Mathematics shares many techniques and topics with computer science, but is more general. In some sense, CS is the mathematics of computing. • Logic is a formal system of reasoning, and studies principles that lay at the very basis of computing/reasoning machines, whether it be the hardware (digital logic) or software (verification, AI etc.) levels. The subfield of logic called computability logic provides a systematic answer to the fundamental questions about what can be computed and how. . 17 Related Fields • Lexicography and specialized lexicography focus on the study of lexicographic reference works and include the study of electronic and Internet-based dictionaries. • Linguistics is the study of languages, converging with computer science in such areas as programming language design and natural language processing. 18 Debate over Name There is some debate over whether the name of the field should be computer science or computation science or computing. The first name is the original, traditional name; however it implies that CS studies computers. The second name is more recent, and it implies that CS studies what we do with computers. The third is the most general term including not only what we can do with present-day computers but any computing process that any physical system can perform. 19 Major Fields of Importance for CS • • • • • • • • • • Mathematical foundations Theoretical Computer Science Hardware Software Data and Information Systems Computing Methodologies Computer Systems Organization Computer applications Computing Milieux .... 20 Mathematical Foundations • Discrete mathematics (Boolean algebra, Graph theory, Domain theory ..) • Mathematical logic • Probability and Statistics • Information theory • ... 21 Theoretical Computer Science • • • • • Algorithmic information theory Computability theory Cryptography Formal semantics Theory of computation (or theoretical computer science) – analysis of algorithms and problem complexity – logics and meanings of programs – Mathematical logic and Formal languages • Type theory • ... 22 Hardware • • • • • • Control structures and Microprogramming Arithmetic and Logic structures Memory structures Input/output and Data communications Logic Design Integrated circuits – VLSI design • Performance and reliability • ... 23 Software • Computer programming (Programming techniques, Program specification, Program verification) • Software engineering – Optimization – Software metrics – Software Configuration Management (SCM) – Structured programming – Object orientation – Design patterns – Documentation • Programming languages • Operating Systems • Compilers • ... 24 Computer Systems Organization • • • • • • Computer architecture Computer networks Distributed computing Performance of systems Computer system implementation ... 25 Data and Information Systems • • • • • • • Data structures Data storage representations Data encryption Data compression Data recovery Coding and Information theory Files – File formats • Information systems – Databases – Information Storage and retrieval – Information Interfaces and Presentation • Data recovery • ..... 26 Computing Methodologies • • • • • • • • • Symbolic and Algebraic manipulation Artificial intelligence Computer graphics Image processing and computer vision Pattern recognition Simulation and Modeling Document and text processing Digital signal processing ... 27 Computer Applications • Administrative data processing • Mathematical software (Numerical analysis, Automated theorem proving, Computer algebra systems) • Physical sciences and Engineering (Computational chemistry, Computational physics) • Life and medical sciences (Bioinformatics, Computational Biology, Medical informatics) • Social and behavioral sciences • Arts and Humanities • Computer-aided engineering • Human-computer interaction (Speech synthesis, Usability engineering) • Robotics 28 • .... Computing Aspects (Milieus) • • • • • • • Computer industry Computers and education Computers and society Legal aspects of computing Management of computing and Information systems Personal computing Computer and information security 29 Computing • CS != Programming • CS >> Programming • Computing != CS • Computing >> CS 30 Big ideas in Computer Science and Engineering Prof. Gerry Sussman [MIT] said we could write down all the ideas in computer science on 4 pages! CS has added valuable knowledge to our understanding of the world. CS discipline offers some important concepts which it is useful for everyone to understand. Just as there is a utility for everyone to understand a certain amount of math and science, there is a good reason for people to understand a certain amount of computer science. http://www.cs.caltech.edu/~andre/general/computer_science.html 31 Big ideas in Computer Science and Engineering Hilbert’s program: Mechanical procedures exist for finding the solutions to problems. That is, for many questions/problems, we can write down a series of steps and simple predicates which define precisely how to find the correct solution. This process is completely mechanical, not requiring any "human" judgment to complete. We can build physical machines which implement these procedures and perform the calculations. There are simple, universal models of computing which capture the basic capabilities of these machines (e.g. automata, pushdown automata, Turing Machines). 32 Big ideas in Computer Science and Engineering The Turing Machine model is "robust" in the sense that "reasonable" additions to it, or alternative formulations of computing models have the same asymptotic power of computability (Church's thesis). “Reasonable" meaning they, for the most part, correspond to things we imagine a real machine could support. In particular, there are stronger models when the machine is allowed to do "unreasonable" things like consult an oracle. Deterministic/guaranteed procedures do not exist for all problems (Halting Problem, uncomputability). An important component of CS theory is to classify problems as computable or uncomputable. 33 Big ideas in Computer Science and Engineering Of the problems which are computable, tasks have different computational difficulty (complexity). An important component of CS theory allows us to analyze algorithms and assess their complexity. (complexity classes [P,NP,PSPACE, IP, ...], order analysis [O(), Omega(), Theta()]) Common idioms/solution techniques, e.g. – divide-and-conquer – linear programming – dynamic programming – graph algorithms 34 Big ideas in Computer Science and Engineering There are alternatives to directly solving hard problems optimally. CS theory also tells us what we can give up in the guarantee of solution quality to reduce computational complexity. – approximation algorithms – online algorithms – polynomial heuristic solutions – randomized algorithms 35 Big ideas in Computer Science and Engineering The desired computation can be captured precisely and unambiguously. Computer science deals with how we construct languages to describe computations, and how we make them convenient for human use. • languages • syntax (grammars) • semantics (denotational, operational) 36 Big ideas in Computer Science and Engineering We do not have to emulate the user's description of a computation to implement it correctly. We simply need to implement a computation which gives the same visible result (has the same meaning) as the user's computation (compilation, CAD) which means semantic transformations. 37 Big ideas in Computer Science and Engineering The representation used for data in a computation can have a big effect on efficiency of operation and ease of human comprehension • effects on computational and storage efficiency (e.g. arrays and fixed structures vs. tagged lists, red-black trees; sparse vs. dense representations of data) • easing human comprehension (e.g. rich data structures) 38 Big ideas in Computer Science and Engineering Our physical world allows us to build very large computer systems. The practical limit to the useful size of a computer system (or at least, the size of the function efficiently supported by a computer system) is almost always human comprehension, not the physical capacity required. Consequently, a major concern of computer science is techniques to manage and reduce complexity (abstractions/information hiding, modularity, problem decomposition, hierarchy, component isolation, invariants, common idioms/paradigms for organization (e.g. procedures, frames, streams, objects, APIs, servers) 39 Big ideas in Computer Science and Engineering • A computing machine can be implemented out of X. • X=mechanical interactions, relays, tubes, transistors, DNA, molecules... • common/useful abstractions (e.g. digital abstraction, flops, memory, communication channels) • disciplines achieving correctness in the face of noise/uncertainty (e.g. voltage levels, timing models and disciplines) 40 Big ideas in Computer Science and Engineering We can extend our notion of abstraction/information hiding to machine design. In particular, the machine code and operating environment for a machine represents the abstract interface it provides to the outside world. Any implementation which provides the same semantics to the machine code is viable. Consequently, we have the notion of ISAs or architecture families which all run the same machine code but which admit to a variety of implementations (e.g. IBM 360, VAX, MIPS, SPARC, x86). 41 Big ideas in Computer Science and Engineering Machine code is just another language specifying precisely the computation to be performed. – a computational engine need only provide the intended semantics, leaving it plenty of freedom as to how it implements the semantics. – like any other language, it can be translated from the input format to another native format (perhaps another machine's native machine format) as long as it provides the original semantics (e.g. softPC, binary translation) 42 Big ideas in Computer Science and Engineering The engineering side of computer science is about: How do we minimize the resources we use in order to perform a computation (set of computations). Physical machines have finite/limited real resources so time, energy, area (hardware: memory, wires)… must be minimized. 43 Big ideas in Computer Science and Engineering We can provide the abstraction of more physical resources by virtualizing the physical resources. That is, sharing the physical resource among multiple uses over time. To accomplish this, we store the state of a particular usage of the physical resources in cheaper storage, e.g. virtual memory, virtual channels, multitasking, time-sharing 44 Big ideas in Computer Science and Engineering Computations occur at different time scales (rates). To minimize work, when possible, hoist a computation out of a high rate region into a slower region. A trivial example: loop invariants/hoisting. 45 Big ideas in Computer Science and Engineering Feedback is the key to diagnosing discrepancies between one's model of the world and reality. This is really just the heart of the scientific method. It should be used by developers to improve programs (debug functional problems, identify and improve performance problems). Moreover, it can be embedded in programs so that they adapt to their data and environment. 46 Big ideas in Computer Science and Engineering A data structure or computation can either be dynamic or static. • Static structures and computations can be very efficient when the size and shape of the computation is constant or has little variance. • Dynamic structures/computations are necessary when the size or scope of the problem is unbounded. They cost more per element or item, but they only have to be as large (as complex) as a particular problem instance. 47 Big Ideas of Engineering There are many big ideas in engineering, e.g. • iterative design • real-world constraints • tradeoffs • feedback • complexity management techniques that are important for understanding not only classical engineered systems but also for understanding social systems and the natural world. 48 History of Ideas of Computer Science • • • • • • • • LEIBNIZ: LOGICAL CALCULUS BOOLE: LOGIC AS ALGEBRA FREGE: MATEMATICS AS LOGIC CANTOR: INFINITY HILBERT: PROGRAM FOR MATHEMATICS GÖDEL: END OF HILBERTS PROGRAM TURING: UNIVERSAL AUTOMATON VON NEUMAN: COMPUTER http://web.clas.ufl.edu/users/rhatch/pages/10-HisSci/links/ H I S T O R Y O F S C I E N C E LINKS 49 C u ltu re L o g ic (R elig io n , A rt, … ) 5 & M a th em a tics 1 CS N atu ral S cien ces (P hy sics, C h em istry , B iology , … ) 2 S ocial S cien ces (E co n o m ics, S o ciolo g y, A n th ro p o lo g y, … ) 3 T h e H u m an ities (P hilo so p h y, H isto ry, L in g u istics … ) 4 The whole is more than the sum of its parts. Aristotle, Metaphysica 21 50 Leibniz: Logical Calculus Gottfried Wilhelm von Leibniz Born: 1 July 1646 in Leipzig, Saxony (now Germany) Died: 14 Nov 1716 in Hannover, Hanover (now Germany) 51 Leibniz´s Calculating Machine “For it is unworthy of excellent men to lose hours like slaves in the labor of calculation which could safely be relegated to anyone else if the machine were used.” 52 Leibniz´s Logical Calculus DEFINITION 3. A is in L, or L contains A, is the same as to say that L can be made to coincide with a plurality of terms taken together of which A is one. B N = L signifies that B is in L and that B and N together compose or constitute L. The same thing holds for larger number of terms. AXIOM 1. B N = N B. POSTULATE. Any plurality of terms, as A and B, can be added to compose A B. AXIOM 2. A A = A. PROPOSITION 5. If A is in B and A = C, then C is in B. PROPOSITION 6. If C is in B and A = B, then C is in A. PROPOSITION 7. A is in A. (For A is in A A (by Definition 3). Therefore (by Proposition 6) A is in A.) …. PROPOSITION 20. If A is in M and B is in N, then A B is in M N. 53 Boole: Logic as Algebra George Boole Born: 2 Nov 1815 in Lincoln, Lincolnshire, England Died: 8 Dec 1864 in Ballintemple, County Cork, Ireland 54 George Boole is famous because he showed that rules used in the algebra of numbers could also be applied to logic. • This logic algebra, called Boolean algebra, has many properties which are similar to "regular" algebra. • These rules can help us to reduce an expression to an equivalent expression that has fewer operators. 55 Properties of Boolean Operations A AND B A B A OR B A + B 56 Frege: Matematics as Logic Friedrich Ludwig Gottlob Frege Born: 8 Nov 1848 in Wismar, Mecklenburg-Schwerin (now Germany) Died: 26 July 1925 in Bad Kleinen, Germany 57 The Predicate Calculus (1) • • In an attempt to realize Leibniz’s ideas for a language of thought and a rational calculus, Frege developed a formal notation (Begriffsschrift). He has developed the first predicate calculus: a formal system with two components: a formal language and a logic. 58 The Predicate Calculus (2) The formal language Frege designed was capable of expressing: – predicational statements of the form ‘x falls under the concept F’ and ‘x bears relation R to y’, etc., – complex statements such as ‘it is not the case that ...’ and ‘if ... then ...’, and – ‘quantified’ statements of the form ‘Some x is such that ...x...’ and ‘Every x is such that ...x...’. 59 The Analysis of Atomic Sentences and Quantifier Phrases Fred loves Annie. Therefore, some x is such that x loves Annie. Fred loves Annie. Therefore, some x is such that Fred loves x. Both inferences are instances of a single valid inference rule. 60 Proof As part of his predicate calculus, Frege developed a strict definition of a ‘proof’. In essence, he defined a proof to be any finite sequence of well-formed statements such that each statement in the sequence either is an axiom or follows from previous members by a valid rule of inference. 61 Cantor: Infinity Georg Ferdinand Ludwig Philipp Cantor Born: 3 March 1845 in St Petersburg, Russia Died: 6 Jan 1918 in Halle, Germany 62 Infinities Set of integers has an equal number of members as the set of even numbers, squares, cubes, and roots to equations! The number of points in a line segment is equal to the number of points in an infinite line, a plane and all mathematical space! The number of transcendental numbers, values such as and e that can never be the solution to any algebraic equation, were much larger than the number of integers. 63 Hilbert described Cantor's work as:- ´...the finest product of mathematical genius and one of the supreme achievements of purely intellectual human activity.´ 64 Hilbert: Program for Mathematics David Hilbert Born: 23 Jan 1862 in Königsberg, Prussia (now Kaliningrad, Russia) Died: 14 Feb 1943 in Göttingen, Germany 65 Hilbert's program Provide a single formal system of computation capable of generating all of the true assertions of mathematics from “first principles” (first order logic and elementary set theory). Prove mathematically that this system is consistent, that is, that it contains no contradiction. This is essentially a proof of correctness. If successful, all mathematical questions could be established by mechanical computation! 66 Gödel: End of Hilberts Program Kurt Gödel Born: 28 April 1906 in Brünn, Austria-Hungary (now Brno, Czech Republic) Died: 14 Jan 1978 in Princeton, New Jersey, USA 67 Incompleteness Theorems 1931 Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. In any axiomatic mathematical system there are propositions that cannot be proved or disproved within the axioms of the system. In particular the consistency of the axioms cannot be proved. 68 Turing: Universal Automaton Alan Mathison Turing Born: 23 June 1912 in London, England Died: 7 June 1954 in Wilmslow, Cheshire, England 69 When war was declared in 1939 Turing moved to work full-time at the Government Code and Cypher School at Bletchley Park. Together with another mathematician W G Welchman, Turing developed the Bombe, a machine based on earlier work by Polish mathematicians, which from late 1940 was decoding all messages sent by the Enigma machines of the Luftwaffe. 70 At the end of the war Turing was invited by the National Physical Laboratory in London to design a computer. His report proposing the Automatic Computing Engine (ACE) was submitted in March 1946. Turing returned to Cambridge for the academic year 194748 where his interests ranged over topics far removed from computers or mathematics, in particular he studied neurology and physiology. 71 1948 Newman (professor of mathematics at the University of Manchester) offered Turing a readership there. Work was beginning on the construction of a computing machine by F C Williams and T Kilburn. The expectation was that Turing would lead the mathematical side of the work, and for a few years he continued to work, first on the design of the subroutines out of which the larger programs for such a machine are built, and then, as this kind of work became standardized, on more general problems of numerical analysis. 72 1950 Turing published Computing machinery and intelligence in Mind 1951 elected a Fellow of the Royal Society of London mainly for his work on Turing machines by 1951 working on the application of mathematical theory to biological forms. 1952 he published the first part of his theoretical study of morphogenesis, the development of pattern and form in living organisms. 73 Von Neuman: Computer John von Neumann Born: 28 Dec 1903 in Budapest, Hungary Died: 8 Feb 1957 in Washington D.C., USA 74 In the middle 30's, Neumann was fascinated by the problem of hydrodynamical turbulence. The phenomena described by non-linear differential equations are baffling analytically and defy even qualitative insight by present methods. Numerical work seemed to him the most promising way to obtain a feeling for the behaviour of such systems. This impelled him to study new possibilities of computation on electronic machines ... 75 Von Neumann was one of the pioneers of computer science making significant contributions to the development of logical design. Working in automata theory was a synthesis of his early interest in logic and proof theory and his later work, during World War II and after, on large scale electronic computers. Involving a mixture of pure and applied mathematics as well as other sciences, automata theory was an ideal field for von Neumann's wide-ranging intellect. He brought to it many new insights and opened up at least two new directions of research. 76 He advanced the theory of cellular automata, advocated the adoption of the bit as a measurement of computer memory, and solved problems in obtaining reliable answers from unreliable computer components. 77 Computer Science Hall of Fame Charles Babbage Julia Robinson Ada Countess of Lovelace Noam Chomsky Axel Thue Juris Hartmanis Stephen Kleene John Brzozowski 78 Computer Science Hall of Fame Richard Karp Stephen Cook Donald Knuth Sheila Greibach Manuel Blum Leonid Levin 79 Women in Computer History • • • • • • • • • • • • Ada Byron King, Countess of Lovelace (1815-1852) Edith Clarke (1883-1959) Rósa Péter (1905-1977) Grace Murray Hopper (1906-1992) Alexandra Illmer Forsythe (1918-1980) Evelyn Boyd Granville Margaret R. Fox Erna Schneider Hoover Kay McNulty Mauchly Antonelli Alice Burks Adele Goldstine Joan Margaret Winters 80 Ada Byron King, Countess of Lovelace (1815-1852) Ada heard in November, 1834, Babbage's ideas for a new calculating engine, the Analytical Engine. Ada was touched by the "universality of Babbages ideas". Hardly anyone else was. In her article, published in 1843, Lady Lovelace's far-sighted comments included her predictions that such a machine might be used to compose complex music, to produce graphics, and would be used for both practical and scientific use. Ada suggested to Babbage writing a plan for how the engine might calculate Bernoulli numbers. This plan, is now regarded as the first "computer program." A software language was named "Ada" in her honor in 1979. 81 Edith Clarke (1883-1959) Edith Clarke is well-known in the field of Power Engineering. Her main contribution to the field was the development of tables that speeded up calculations for engineers. This was especially important because she created them during World War I, when engineers desperately needed to work faster. 82 Rósa Péter (1905-1977) Her first research topic was number theory, but she became discouraged on finding that her results had already been proved by Dickson. For a while Rósa wrote poetry, but around 1930 she was encouraged to return to mathematics by Kalmár. He suggested Rósa examine Gödel's work, and in a series of papers she became a founder of recursive function theory. Rósa wrote Recursive Functions in 1951, which was the first book on the topic and became a standard reference. In 1952 Kleene described Rósa Péter in a paper in Bull. Amer. Math. Soc. as ``the leading contributor to the special theory of recursive functions." From the mid 1950's she applied recursive function theory to computers. In 1976 her last book was on this topic: Recursive Functions in Computer Theory. 83 ENIAC Ladies 84 Erna Schneider Hoover Invention: Computerized Telephone Switching System Erna Schneider earned a B.A. with honors in medieval history from Wellesley College, and later a Ph.D. in the philosophy and foundations of mathematics from Yale University. In 1954, after teaching for a number of years at Swarthmore College, she began a research career at Bell Laboratories. While there, she invented a computerized switching system for telephone traffic, to replace existing hard-wired, mechanical switching equipment. For this ground-breaking achievement -the principles of which are still used today -- she was awarded one of the first software patents ever issued (Patent #3,623,007, Nov. 23, 1971) . At Bell Labs, she became the first female supervisor of a technical department. 85 Grace Murray Hopper (1906-1992) Grace Murray Hopper: Inventor of the Computer Compiler She participated in the development of the Common Business-Oriented Language (COBOL; 1959-61) for the UNIVAC The very first computer bug: Grace Murray Hopper originated this term when she found a real bug in a computer 86 Ida Rhodes (1900 -1986) She designed the C-10 language in the early 1950 for the UNIVAC. She also designed the original computer used for the Social Security Administration. In 1949, the department of Commerce awarded her an exceptional Service Gold Medal for significant pioneering leadership and outstanding contributions to the scientific progress of the nation. 87 Evelyn Boyd Granville Evelyn Boyd Granville - was one of the first African American women to earn a Ph.D. in Mathematics. She became a specialist in rocket and missile fuses, orbit computations and trajectory calculations for national defense and the space program providing technical support for the Vanguard, Mercury and Apollo projects. In addition, she served as an educational consultant to the State of California, helping to improve the teaching of math in elementary and secondary schools. 88 Jean E. Sammet She initiated the concept and directed the development of the first FORMAC (FORmula MAnipulation Compiler). FORMAC was the first widely used general language. It was also the first system for manipulating nonnumeric algebraic expressions. In 1965, she became programming language technology manager in the IBM Systems Development Division. Afterward, she wrote a book on programming languages. Her book, Programming Languages: History and Fundamentals, was published by Prentice-Hall in 1969. 89 Dr. Thelma Estrin Professor Emerita Now retired from University of California, Los Angeles, where she was a computer science professor, Estrin was a pioneer in the field of biomedical engineering who realized that some of the most important ideas in science did not fit neatly into separate fields. Her work would combine concepts from anatomy, physiology, and neuroscience with electronic technology and electrical engineering. She was one of the first to use computer technology to solve problems in health care and in medical research. Estrin designed and then implemented the first system for analog-digital conversion of electrical activity from the nervous system," a precursor to the use of computers in medicine. She published papers on how to map the brain with the help of computers, and long before the Internet became popular and easy to use, she designed a computer network between UCLA and UC Davis in 1975. 90 Dana Angluin B.A., Ph.D. University of California at Berkeley, 1969, 1976, Joined Yale Faculty 1979 Algorithmic models of learning Professor Angluin’s thesis was among the first work to apply complexity theory to the field of inductive inference. Her work on learning from positive data reversed a previous dismissal of that topic, and established a flourishing line of research. Her work on learning with queries established the models and the foundational results for learning with membership queries. Recently, her work has focused on the areas of coping with errors in the answers to queries, maplearning by mobile robots, and fundamental questions in modeling the interaction of a teacher and a learner. 91 Nancy A. Lynch Professor of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. Nancy Lynch heads the Theory of Distributed Systems Group (TDS) research group in MIT's Laboratory for Computer Science. This group is part of the Theory of Computation (TOC) group and also of the Principles of Computer Systems (POCS) group. Teaching - Spring 2001: 6.897 Modeling and Analyzing Really Complicated Systems, Using State Machines Fall 2001 6.852 Distributed Algorithms Research interests: distributed computing, real-time computing, algorithms, lower bounds, formal modelling and verification. 92 Adele E. Goldberg Adele Goldberg received her Ph.D. from the University of California at Berkeley in 1992. She is an associate professor in the UIUC Department of Linguistics and a part-time Beckman Institute faculty member in the Cognitive Science Group. Her fields of professional interest are syntax/semantics, constructional approaches to grammar, lexical semantics, language acquisition, language processing, and categorization. 93 Sandra L. Kurtzig In today's male-dominated software industry, women founders and CEOs (chief executive officers) are practically nonexistent. But while software titans like Bill Gates and Oracle's Larry Ellison have become the poster boys for Silicon Valley success, the first multimillion-dollar software entrepreneur was a woman. Starting with just $2,000, Sandra Kurtzig built a software empire that, at its peak, boasted around $450 million in annual sales. And it all started as a part-time job. 94 International Difference in Percentage of Female Students within Informatics 2001 Country England Italy, France, Spain, Portugal Former Sowjetunion Bulgaria %Women 35 40 50 50 60-70 Grece 59 India, Malaysia, Singapure 50 Germany 8 Olga Goldmann, Seminar: Geschichte der Informatik http://www.millo.de/virtosphere/schillo/teaching/WS2001/Vortraege/Frauen.ppt 95 Philosophical Problems of Computing Fleming's original thermionic valve, 1889. Science Museum London 96 Babbage's Difference Engine No 1, 1832. Front detail. Science Museum London 97 The 'Bombe' code-breaking machine, 1943 at Bletchley Park in Bedfordshire, the British forces' intelligence centre during WWII. The cryptographers at Bletchley Park deciphered top- secret military communiques between Hitler and his armed forces. These communiques were encrypted in the 'Enigma' code which the Germans considered unbreakable. However, the codebreakers at Bletchley cracked the code with the help of the Bombe machine. 98 Code-breaking personnel at Bletchley Park, 1943. This shows one of the Hut 3 priority teams at Bletchley Park, in which civilian and service personnel worked together at code- breaking. 99 Wrens* operating the 'Colossus' computer, 1943. Colossus was the world's first electronic programmable computer, at Bletchley Park in Bedfordshire. * Women's Royal Naval Service 100 The computer presents itself as a culturally defining technology and has become a symbol of the new millennium, playing a cultural role far more influential than the mills in the Middle Ages, mechanical clocks in the seventeenth century, or the steam engine in the age of the industrial revolution. (Bolter 1984) 101 “The important difference is that the computer (the physical object that is directly related to the theory) is not a focus of investigation (not even it he sense of being the cause of certain algorithm proceeding in certain way) but it is rather theory materialized, a tool always capable of changing in order to accommodate even more powerful theoretical concepts. ” Scientific Methods in Computer Science, GDC 102 Philosophy of Computing or Philosophy of Information? DICHOTOMY INFORMATION – COMPUTATION SUBSTANTIVE - VERB DATA STRUCTURE – FUNCTION/ALGORITHM PARTICLE – FORCE (FIELD) Instructive analogy from physics: ATOMISM PARTICLES are considered as the primary principle. FIELDS/INTERACTIONS are defined in terms of particles, particle exchange. 103 What Is Information? Luciano Floridi There is no consensus yet on the definition of semantic information. The Standard Definition of declarative, objective and semantic Information (SDI): information = meaningful data Floridis main thesis is that meaningful and well-formed data constitute information only if they also qualify as contingently truthful. Now the problem is to interpret what contingently truthful means in this context. "The contingent, roughly speaking, is what has the ground of its being not in itself but in somewhat else. Such is the aspect under which actuality first comes before consciousness . . . But the contingent is only one side of the actual . . . . It is the actual, in the signification of something merely possible. Accordingly we consider the contingent to be what may or may not be, what may be in one way or another, whose being or not-being, and whose being on this wise or otherwise, depends not upon itself but on something else. To overcome this contingency is . . .the problem of science . . . ." Logic, § 145 Note. www.class.uidaho.edu/mickelsen/texts/Hegel%20Glossary.htm 104 The Philosophy of Information (PI) A new philosophical discipline, concerned with a) the critical investigation of the conceptual nature and basic principles of information, including its dynamics (especially computation and flow), utilisation and sciences; and b) the elaboration and application of information-theoretic and computational methodologies to philosophical problems. L. Floridi "What is the Philosophy of Information?", Metaphilosophy, 2002 http://www.wolfson.ox.ac.uk/~floridi/papers.htm 105 What is Computation? Brian Cantwell Smith 106 The Age of Significance Volume I • Introduction Brian Cantwell Smith 107 Construals of Computation 1. Formal symbol manipulation (FSM): the idea, derivative from a century’s work in formal logic and metamathematics, of a machine manipulating (at least potentially) symbolic or meaningful expressions without regard to their interpretation´or semantic content; 2. Calculation of a function (FUN): behavior that, when given as input an argument to a (typically mathematical) function, produces as output the value of that function on that argument. 3. Effective computability (EC): what can be done—and how hard it is to do it—mechanically, as it were, by, an abstract analogue of a “mere machine”; 108 4. Rule-following or algorithm execution (RF): what is involved, and what behaviour is thereby produced, in following a set of rules or instructions, such as when cooking dessert; 5. Digital state machines (DSM): the idea of an automaton with a finite, disjoint set of internally homogeneous states—as parodied in the “clunk, clunk, clunk” gait of a 1950’s cartoon robot; 6. Information processing (IP): what is involved in storing, manipulating, displaying, and otherwise trafficking in “information,” whatever information might be; and 7. Physical symbol systems (PSS): the idea, made famous by Newell and Simon, that, somehow or other, computers interact with and perhaps are also made of symbols in a way that depends on their mutual physical embodiment. 109 Church-Turing Thesis* *Source: Stanford Encyclopaedia of Philosophy (B. Jack Copeland) 110 A Turing machine is an abstract representation of a computing device. It is more like a computer program (software) than a computer (hardware). 111 LCMs [logical computing machines: Turing’s expression for Turing machines] were first proposed by Alan Turing, in an attempt to give a mathematically precise definition of "algorithm" or "mechanical procedure". 112 Effective Computability The Church-Turing thesis concerns an effective or mechanical method in logic and mathematics. 113 A method M is called ‘effective’ or ‘mechanical’ iff: 1. M is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols); 2. M will, if carried out without error, always produce the desired result in a finite number of steps; 3. M can (in principle) be carried out by a human being unaided by any machinery save paper and pencil; 4. M demands no insight or ingenuity on the part of the human being carrying it out. 114 Misunderstandings of the Turing Thesis Turing did not show that his machines can solve any problem that can be solved "by instructions, explicitly stated rules, or procedures" and nor did he prove that a universal Turing machine "can compute any function that any computer, with any architecture, can compute". 115 Turing proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis here called Turing’s thesis. 116 Turing introduces his machines as an idealised description of a certain human activity, the tedious one of numerical computation, which until the advent of automatic computing machines was the occupation of many thousands of people in commerce, government, and research establishments. 117 Turing’s "Machines". These machines are humans who calculate. (Wittgenstein) A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine. (Turing) 118 A thesis concerning the extent of effective methods procedures that a human being unaided by machinery is capable of carrying out - has no implication concerning the extent of the procedures that machines are capable of carrying out, even machines acting in accordance with ‘explicitly stated rules’. 119 Among a machine’s repertoire of atomic operations there may be those that no human being unaided by machinery can perform. 120 Two Most Fundamental Functions SEARCH (identify objects = divide universe in parts) SORT (organize: what is the same, what is different) 121 Repetition, Similarity As repetition is based upon similarity, it must be relative. Two things that are similar are always similar in certain respects. 122 Repetition, Similarity Searching for similarity and differences leads to classifications i.e. the division of objects or events in different groups/classes. The simplest tool by for classification is the binary opposition or dichotomy (dualism). When we use dichotomy, we only decide if an object is of kind A or of kind A. Examples of frequent dichotomies are yes/no, true/false, before/after, more/less, above/below, etc. 123 Identity The basic feature of experimental method is its reproducibility: It must be possible to establish essentially the same experimental situation in order to obtain the same results. This means that the experimental arrangement can be made with essentially equivalent parts. What we call “essentially equivalent” (or we can call it “essentially the same”) depends on situation. Even here the principle of information hiding helps us to get a practical “level of resolution” which means information hiding for all objects below that level. 124 Identity Declaring two systems/particles/states as identical is entirely the matter of focus. For example if we focus on question of how many people in this country are vegetarians, we just treat all people as equal units. If on the other hand we want to know how many women in this country are vegetarian, we discriminate between men and women in our analysis of people, so they are no longer identical. 125 Identity Declaring two systems/particles/states as identical is entirely the matter of focus. 126 Identity We can e.g. assume that bacteria of particular sort are interchangeable (indistinguishable) in certain context. That enables us to make repeated experiments with different agents and to treat all bacteria of the same type as equal. It does not mean that they are identical in the absolute sense. It only means that for our purpose the existing difference does not have any significance. 127 Identity Example of ancient atomic theory. The problem of showing that one single physical body- say piece of iron is composed of atoms is at least as difficult as of showing that all swans are white. Our assertions go in both cases beyond all observational experience. The difficulty with these structural theories is not only to establish the universality of the law from repeated instances as to establish that the law holds even for one single instance. 128 Identity A singular statement like “This swan here is white” may be said to be based on observation. Yet it goes beyond experience- not only because of the word “white”, but because of the word “swan”. For by calling something a “swan”, we attribute to it properties which go far beyond mere observation. So even the most ordinary singular statements are always the interpretations of the facts in the light of theories! 129 Classification (1) – A relation is an equivalence relation if it is reflexive, symmetric and transitive. – An example of such is equality on a set. 130 Classification (2) CLASSES SHOULD BE DISJUNCT ... class2 class 1: positive effect class 2: negative effect class1 class 3: no effect class3 Universe here is a group of patients who test a new medicine. ... AND CHOSEN ACCORDING TO SAME CRITERIA ... 131 Classification (3) Jorge Luis Borges, "The Analytical Language of John Wilkins“ (Incongruity) Borges's fictive encyclopedia divides animals into: (a) those that belong to the Emperor, (b) embalmed ones, (c) those that are trained, (d) suckling pigs, (e) mermaids, (f) fabulous ones, (g) stray dogs, (h) those that tremble as if they were mad, (i) those that resemble flies from a distance (j) those drawn with a very fine camel's hair brush, (k) innumerable ones, (l) others, (m) those that have just broken a flower vase 132 Relations to Natural Philosophers Paradigm Konrad von Megenberg. Buch der Natur (Augsburg, 1481). A medieval Latin compendium of science translated into German in the fourteenth century and was first printed in Augsburg in 1475. (Lessing J. Rosenwald Collection), Lobrary of Congress 133 Universe As An Assemblage Of Natural Objects Rudolf II, patron of Kepler and briefly Brahe was fascinated by alchemy, astrology, and other ways in which human art interfered in or perfected nature. Here one of his court painters has, through art, depicted Rudolf as an assemblage of natural objects: fruits, vegetables, grains, and flowers. Galileo referred contemptuously to such portraits in his Dialogue on Two Chief World Systems. 134 Universe As An Assemblage Of Natural Objects What properties must a system have to be living? Can we make a clear distinction between living and nonliving systems? What is connection between self-organization and life? Two genetically engineered mice, 1988. These male mice are direct descendants of the first transgenic mammals to be granted a US patent. This strain was patented by Harvard University. Science Museum London 135 Philosophy Of Science – A New Paradigm It is time again to direct gaze upward and see Nature as a whole. What have we learned last couple of centuries of scientific specialisation and division to ever smaller fields? Field of computing seems to be the best candidate to replace physics as paradigmatic mirror of Philosophy of Science used to reflect the Universe that matters. This time Universe has to include human, and not only as a machine! Unifying concept of information has even the potential to bring together Sciences and Humanities. New Natural Philosophy? 136 137 A New Kind of Science Stephen Wolfram 138 Santiago Theory - Autopoiesis ”Living systems are cognitive systems, and living as a process is a process of cognition. This statement is valid for all organisms, with and without a nervous system.” Maturana Humberto, Biology of Cognition, 1970 139 INFORMATION COMPUTATION COGNITION 140 Evolutionary Biological Paradigm The most developed forms of computational systems: Evolutive self-organizing self-sustaining complex systems built of metabolic/computational units 141 142 Pieter BRUEGEL, the Elder NA-CAP 2006 @ RPI, Troy, NY, USA North American Computing and Philosophy Conference, August 10-12, 2006 Swedish National Course in Philosophy of Computer Science Gordana Dodig-Crnkovic Mälardalen University Department of Computer Science and Electronics http://www.idt.mdh.se/personal/gdc/ 143 PHILOSOPHY OF COMPUTER SCIENCE CD5650 COURSE OUTLINE http://www.idt.mdh.se/personal/gdc/pi-network.htm http://www.idt.mdh.se/personal/gdc/PI_04/index.html Gordana Dodig-Crnkovic Department of Computer Science and Engineering Mälardalen University, 23 January 2004 144 Interdisciplinary Distance Learning in Computing and Philosophy North American Computers and Philosophy Conference July 26-28, 2007 NA-CAP @ Loyola University Chicago Gordana Dodig-Crnkovic http://www.idt.mdh.se/personal/gdc/ Department of Computer Science and Engineering Mälardalen University, Sweden 145 BASED ON Increasing Interdisciplinarity by Distance Learning: Examples Connecting Economics with Software Engineering, and Computing with Philosophy Gordana Dodig-Crnković, Ivica Crnković e-mentor No 2 (19) / 2007 www.e-mentor.edu.pl/eng and experiences with Swedish national course PHILOSOPHY OF COMPUTER SCIENCE http://www.idt.mdh.se/personal/gdc/pi-network.htm http://www.idt.mdh.se/personal/gdc/PI_04/index.html and course in software engineering and management of software development projects for students of management and economy. 146 146 Distance Interdisciplinary Courses - Internet-based distance undergraduate course in software engineering and management of software development projects for students of management and economy. The goal of the course was to bridge the gap between disciplines of economy (management) and software engineering, transfer knowledge and provide necessary technical background for future managers who very likely in their careers will take part in software intense projects. Both the interdisciplinarity and the advanced e-learning technology of this course made it challenging. - Specialized level Swedish National Course in Philosophy of Computing and Informatics for students of computing, philosophy and design, which was a combination of a campus-based and a distance course involving several Swedish universities, with a group of distinguished teachers from both Sweden and abroad. The critical challenge of this course was the establishing of a new inter-discipline and overarching the gaps between traditions of disciplinary thinking. 147 • • • It is interesting to compare the experiences of two different courses aimed at strengthening interdisciplinary and crossdisciplinary competence and learning practices. The course in software engineering for managers was necessarily focused towards implementations and practical applications. The ambition to provide future managers and economists with a holistic view of management of software-intense projects turned out not to be simple to realize. Taking a holistic approach goes beyond exchanging basic facts between different knowledge communities. In many cases the basic facts are not sufficient to adequately describe specific cases of interest. Not only technical matters but also many informal, cultural factors can be expected to constitute barriers to reaching a common understanding between fields which are so far from each other that they usually 148 do not communicate directly. COMPUTING AND PHILOSOPHY ARTS PHILOSOPH Y COMP. ENG. COMPUTER SCIENCE COMPUTING 149 149 LECTURES – PART I 22 January 09-12 Introduction to Philosophy of Information – Luciano Floridi 13-14 Discussion on Introduction to PI 14-15 Physics as an “Ideal Science” Philosophical Foundations and Consequences Lars-Göran Johansson 15-17 The Function of Natural Laws in Physics Lars-Göran Johansson 23 January 09-12 Philosophical Foundations of Computability Gordana Dodig-Crnkovic 13-14 Discussion on Phil. Found. of Computability 14-15 Planning for the Course and Mini-Conference Closing Remarks (GDC) 150 150 LECTURES – PART II 04 March 09-12 Methodological Foundations of CS Erik Sandewall 13-14 Discussion on Meth. Found. of CS 14-15 Critical Analysis of CS Methodology Björn Lisper, Jan Gustafsson 15-16 Discussion on Critical Analysis of CS Methodology, Björn Lisper, Jan Gustafsson 05 March 09-12 Modelling and Simulation Kimmo Eriksson, Lars-Göran Johansson 13-14 Discussion on Modelling and Simulation 14-15 DISCUSSION OF PAPER DRAFTS (GDC) 15-16 Closing Remarks 151 151 LECTURES – PART III 13 May 09-12 Ethics and Professional Issues in Computing Gordana Dodig-Crnkovic 13-14 Discussion on Ethics and Professional Issues in Computing 14-15 Ethics and AI (Peter Funk) 15-16 Discussion on Ethics and AI 14 May 09-16 MINI-CONFERENCE 16-17 Closing Remarks 152 152 PI NETWORK Ahonen-Jonnarth Ulla Senior Lecturer, CS/Biology, Gävle University Dodig-Crnkovic Gordana Senior Lecturer, CS/Physics, Mälardalen University Gustafsson Jan Senior Lecturer Computer Science, Mälardalen University Funk Peter Senior Lecturer (docent) Artificial Intelligence Mälardalen University Lager Torbjörn Professor of General and Computational Linguistics, Göteborg University Lisper Björn Professor of Computer Engineering, Mälardalen University Nivre Joakim Professor of Computational Linguistics, Växjö University Odelstad Jan Senior Lecturer (docent) CS/Theoretic Philosophy Gävle University Correspondent: Gang Liu Deputy Director of Philosophy of Science and Technology DivisionInstitute of Philosophy, Chinese Academy of Social SciencesPhD in Philosophy, Beijing 153 153 Why is Philosophy Important for Computing? • ”Thinking tool-box” - access to: – Paradigms – Metaphors – Historical examples (knowledge capital) • Communication – both within computing community and wider • Context – conceptual and cultural framework • Humanist dimensions of higher education are important! • Knowledge society – leads to automated production, organization and even automated discovery. Genuine human thinking abilities including creativity will make the difference! 154 154 Why is Computing Important for Philosophy? • • Simulated or experimental philosophy. Experiments “in silico” (or alternative constructed cognitive/computational systems): As an innovative extension of an ancient tradition of thought experiment, application of computational modeling schemes to questions in logic, epistemology, philosophy of science, philosophy of biology, philosophy of mind, and so on. Computing paradigms and metaphors 155 155 Results from the PI Course • Participants from different universities (Blekinge, Dalarna, Mälardalen, Skövde, Uppsala, SICS Stockholm) have taken part in the course and have presented their research papers at the Mini-conference. These have been documented in the Course Proceedings, http://www.idt.mdh.se/personal/gdc/PI_04/proceedings.pdf • As a result of the course ten papers have been published in journals and conference proceedings or included as chapters in PhD theses. 156 156 Future Work Extended network activity and future, possibly distance, courses in collaboration with colleagues in other countries: - Peter Boltuc, University of Illinois at Springfield; - Vincent Müller, American College of Thessaloniki; - Jordi Vallverdú. Universitat Autònoma de Barcelona; - Teresa Numerico, University of Bologna and the University of Salerno; - Matti Tedre University of Joensuu, Finland, - Russ Abbott, California State University, Los Angeles and a number of colleagues from Swedish Universities). This will certainly broaden our experience and allow us to identify further relevant topics to be included. 157 157 Computation, Information, Cognition: The Nexus and the Liminal Editor(s): Gordana Dodig Crnkovic and Susan Stuart Cambridge Scholars Publishing Titles in Print as of July 2007 http://www.c-s-p.org/Flyers/Computation-Information--Cognition--The-Nexus-and-theLiminal.htm 158 Computation, Information, Cognition: The Nexus and the Liminal Editor(s): Gordana Dodig Crnkovic and Susan Stuart Cambridge Scholars Publishing Titles in Print as of July 2007 http://www.c-s-p.org/Flyers/Computation-Information--Cognition--The-Nexus-and-theLiminal.htm 159 Knowledge Generation as Natural Computation KGCM - International Conference on Knowledge Generation, Communication and Management July 8-11, 2007 – Orlando, Florida, USA. Gordana Dodig-Crnkovic n http://www.idt.mdh.se/personal/gdc/ Department of Computer Science and Engineering Mälardalen University, Sweden 160 Correspondence Principle picture from Stuart A. Umpleby http://www.gwu.edu/~umpleby/recent_papers/2004_what_i_learned_from_heinz_von_foer ster_figures_by_umpleby.htm TM Natural Computation 161 Church-Turing Thesis* *Source: Stanford Encyclopaedia of Philosophy 162 A Turing machine is an abstract representation of a computing device. It is more like a computer program (software) than a computer (hardware). 163 LCMs [Logical Computing Machines: Turing’s expression for Turing machines] were first proposed by Alan Turing, in an attempt to give a mathematically precise definition of "algorithm" or "mechanical procedure". 164 • • • • The Church-Turing thesis concerns an effective or mechanical method in logic and mathematics. 165 • A method, M, is called ‘effective’ or ‘mechanical’ just in case: 1. M is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols); M will, if carried out without error, always produce the desired result in a finite number of steps; M can (in practice or in principle) be carried out by a human being unaided by any machinery except for paper and pencil; M demands no insight or ingenuity on the part of the human being carrying it out. 2. 3. 4. 166 • Turing’s thesis: LCMs [logical computing machines; TMs] can do anything that could be described as "rule of thumb" or "purely mechanical". (Turing 1948) • He adds: This is sufficiently well established that it is now agreed amongst logicians that "calculable by means of an LCM" is the correct accurate rendering of such phrases. 167 • Turing introduced this thesis in the course of arguing that the Entscheidungsproblem, or decision problem, for the predicate calculus - posed by Hilbert in 1928 was unsolvable. 168 • Church’s account of the Entscheidungsproblem • By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system. • 169 • The truth table test is such a method for the propositional calculus. • Turing showed that, given his thesis, there can be no such method for the predicate calculus. 170 • Turing proved formally that there is no TM which can determine, in a finite number of steps, whether or not any given formula of the predicate calculus is a theorem of the calculus. • So, given his thesis that if an effective method exists then it can be carried out by one of his machines, it follows that there is no such method to be found. 171 • Church’s thesis: A function of positive integers is effectively calculable only if recursive. 172 Misunderstandings of the Turing Thesis • Turing did not show that his machines can solve any problem that can be solved "by instructions, explicitly stated rules, or procedures" and nor did he prove that a universal Turing machine "can compute any function that any computer, with any architecture, can compute". 173 • Turing proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis here called Turing’s thesis. 174 • A thesis concerning the extent of effective methods - procedures that a human being unaided by machinery is capable of carrying out - has no implication concerning the extent of the procedures that machines are capable of carrying out, even machines acting in accordance with ‘explicitly stated rules’. 175 • Among a machine’s repertoire of atomic operations there may be those that no human being unaided by machinery can perform. 176 • Turing introduces his machines as an idealised description of a certain human activity, the one of numerical computation, which until the advent of automatic computing machines was the occupation of many thousands of people in commerce, government, and research establishments. • 177 • Turing’s "Machines". These machines are humans who calculate. (Wittgenstein) • A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine. (Turing) 178 • The Entscheidungsproblem is the problem of finding a humanly executable procedure of a certain sort, and Turing’s aim was precisely to show that there is no such procedure in the case of predicate logic. 179 Other Models of Computation 180 Models of Computation • Turing Machines • Recursive Functions • Post Systems • Rewriting Systems 181 Turing’s Thesis A computation is mechanical if and only if it can be performed by a Turing Machine. Church’s Thesis (extended) All models of computation are equivalent. 182 Post Systems • Axioms • Productions Very similar to unrestricted grammars. 183 Theorem: A language is recursively enumerable if and only if it is generated by a Turing Machine. 184 Theorem: A language is recursively enumerable if and only if it is generated by a recursive function. 185 Post Systems Example: Unary Addition Axiom: 1 1 11 Productions: V1 V 2 V 3 V11 V 2 V 3 1 V1 V 2 V 3 V1 V 2 1 V 3 1 186 A production: V1 V 2 V3 V11 V 2 V3 1 1 1 11 11 1 111 11 11 1111 V1 V 2 V3 V1 V 2 1 V3 1 187 Post systems are good for proving mathematical statements from a set of Axioms. 188 Theorem: A language is recursively enumerable if and only if it is generated by a Post system. 189 Rewriting Systems They convert one string to another • Matrix Grammars • Markov Algorithms • Lindenmayer-Systems (L-Systems) Very similar to unrestricted grammars. 190 Matrix Grammars Example: P1 : S S1 S 2 P2 : S1 aS 1 , S 2 bS 2 c P3 : S1 , S 2 Derivation: S S1 S 2 aS 1bS 2 c aaS 1bbS 2 cc aabbcc A set of productions is applied simultaneously. 191 P1 : S S1 S 2 P2 : S1 aS 1 , S 2 bS 2 c P3 : S1 , S 2 n n n L { a b c : n 0} 192 Theorem: A language is recursively enumerable if and only if it is generated by a Matrix grammar. 193 Markov Algorithms Grammars that produce Example: ab S aSb S S Derivation: aaabbb aaSbb aSb S 194 ab S aSb S S n n L { a b : n 0} * In general: L {w : w } 195 Theorem: A language is recursively enumerable if and only if it is generated by a Markov algorithm. 196 Lindenmayer-Systems They are parallel rewriting systems Example: a aa Derivation: a aa aaaa aaaaaaaa L {a 2 n : n 0} 197 Lindenmayer-Systems are not general as recursively enumerable languages Extended Lindenmayer-Systems: ( x, a, y ) u context Theorem: A language is recursively enumerable if and only if it is generated by an Extended Lindenmayer-System. 198 L-System Example: Fibonacci numbers • Consider the following simple grammar: • • • • • • variables : A B constants : none start: A rules: A B B AB 199 • This L-system produces the following sequence of strings ... • • • • • • • • Stage 0 : A Stage 1 : B Stage 2 : AB Stage 3 : BAB Stage 4 : ABBAB Stage 5 : BABABBAB Stage 6 : ABBABBABABBAB Stage 7 : BABABBABABBABBABABBAB 200 • If we count the length of each string, we obtain the Fibonacci sequence of numbers : • 1 1 2 3 5 8 13 21 34 .... 201 Example - Algal growth The figure shows the pattern of cell lineages found in the alga Chaetomorpha linum. To describe this pattern, we must let the symbols denote cells in different states, rather than different structures. 202 • This growth process can be generated from an axiom A and growth rules • • • • • A DB BC CD DE E A 203 Here is the pattern generated by this model. It matches the arrangement of cells in the original alga. • • • • • • • • • • • • Stage 0 : A Stage 1 : D B Stage 2 : E C Stage 3 : A D Stage 4 : D B E Stage 5 : E C A Stage 6 : A D D B Stage 7 : D B E E C Stage 8 : E C A A D Stage 9 : A D D B D B E Stage 10 : D B E E C E C A Stage 11 : E C A A D A D D B 204 Example - a compound leaf (or branch) • • • • • • • • • • • • • • • • Leaf1 { ; Name of the l-system, "{" indicates start ; Compound leaf with alternating branches, angle 8 ; Set angle increment to (360/8)=45 degrees axiom x ; Starting character string a=n ; Change every "a" into an "n" n=o ; Likewise change "n" to "o" etc ... o=p p=x b=e e=h h=j j=y x=F[+A(4)]Fy ; Change every "x" into "F[+A(4)]Fy" y=F[-B(4)]Fx ; Change every "y" into "F[-B(4)]Fx" F=@1.18F@i1.18 } ; final } indicates end 205 http://www.xs4all.nl/~cvdmark/tutor.html (Cool site with animated L-systems) 206 Here is a series of forms created by slowly changing the angle parameter. lsys00.ls Check the rest of the Gallery of L-systems: http://home.wanadoo.nl/laurens.lapre/ 207 Plant Reception Environment Response Internal processes Internal processes Response Reception A model of a horse chestnut tree inspired by the work of Chiba and Takenaka. Here branches compete for light from the sky hemisphere. Clusters of leaves cast shadows on branches further down. An apex in shade does not produce new branches. An existing branch whose leaves do not receive enough light dies and is shed from the tree. In such a manner, the competition for light controls the density of branches in the tree crowns. 208 Plant Environment Reception Response Internal processes Internal processes Response Reception 209 Apropos adaptive reactive systems: "What's the color of a chameleon put onto a mirror?" -Stewart Brand (Must be possible to verify experimentally, isn’t it?) 210 Fundamental Limits of Computation 211 Biological Computing 212 DNA Based Computing • Despite their respective complexities, biological and mathematical operations have some similarities: • The very complex structure of a living being is the result of applying simple operations to initial information encoded in a DNA sequence (genes). • All complex math problems can be reduced to simple operations like addition and subtraction. 213 • For the same reasons that DNA was presumably selected for living organisms as a genetic material, its stability and predictability in reactions, DNA strings can also be used to encode information for mathematical systems. 214 The Hamiltonian Path Problem • The objective is to find a path from start to end going through all the points only once. • This problem is difficult for conventional (serial logic) computers because they must try each path one at a time. It is like having a whole bunch of keys and trying to see which fits a lock. 215 • Conventional computers are very good at math, but poor at "key into lock" problems. DNA based computers can try all the keys at the same time (massively parallel) and thus are very good at key-into-lock problems, but much slower at simple mathematical problems like multiplication. • The Hamiltonian Path problem was chosen because every key-intolock problem can be solved as a Hamiltonian Path problem. 216 Solving the Hamiltonian Path Problem 1. 2. 3. 4. 5. Generate random paths through the graph. Keep only those paths that begin with the start city (A) and conclude with the end city (G). Because the graph has 7 cities, keep only those paths with 7 cities. Keep only those paths that enter all cities at least once. Any remaining paths are solutions. 217 Solving the Hamiltonian Path Problem • The key to solving the problem was using DNA to perform the five steps in the above algorithm. • These interconnecting blocks can be used to model DNA: • 218 • DNA tends to form long double helices: • • The two helices are joined by "bases", represented here by coloured blocks. Each base binds only one other specific base. In our example, we will say that each coloured block will only bind with the same colour. For example, if we only had red blocks, they would form a long chain like this: • • Any other colour will not bind with red: • • • • • 219 Programming with DNA • Step 1: Create a unique DNA sequence for each city A through G. For each path, for example, from A to B, create a linking piece of DNA that matches the last half of A and first half of B: • • Here the red block represents city A, while the orange block represents city B. The half-red half-orange block connecting the two other blocks represents the path from A to B. • In a test tube, all the different pieces of DNA will randomly link with each other, forming paths through the graph. 220 • Step 2: Because it is difficult to "remove" DNA from the solution, the target DNA, the DNA which started at A and ended at G was copied over and over again until the test tube contained a lot of it relative to the other random sequences. • This is essentially the same as removing all the other pieces. Imagine a sock drawer which initially contains one or two coloured socks. If you put in a hundred black socks, chances are that all you will get if you reach in is black socks! 221 • Step 3: Going by weight, the DNA sequences which were 7 "cities" long were separated from the rest. • A "sieve" was used which allows smaller pieces of DNA to pass through quickly, while larger segments are slowed down. The procedure used actually allows you to isolate the pieces which are precisely 7 cities long from any shorter or longer paths. 222 • Step 4: To ensure that the remaining sequences went through each of the cities, "sticky" pieces of DNA attached to magnets were used to separate the DNA. • The magnets were used to ensure that the target DNA remained in the test tube, while the unwanted DNA was washed away. First, the magnets kept all the DNA which went through city A in the test tube, then B, then C, and D, and so on. In the end, the only DNA which remained in the tube was that which went through all seven cities. 223 • Step 5: All that was left was to sequence the DNA, revealing the path from A to B to C to D to E to F to G. 224 Advantages • The above procedure took approximately one week to perform. Although this particular problem could be solved on a piece of paper in under an hour, when the number of cities is increased to 70, the problem becomes too complex for even a supercomputer. • While a DNA computer takes much longer than a normal computer to perform each individual calculation, it performs an enormous number of operations at a time (massively parallel). 225 • DNA computers also require less energy and space than normal computers. 1000 litres of water could contain DNA with more memory than all the computers ever made, and a pound of DNA would have more computing power than all the computers ever made. 226 The Future • DNA computing is less than ten years old and for this reason, it is too early for either great optimism of great pessimism. • Early computers such as ENIAC filled entire rooms, and had to be programmed by punch cards. Since that time, computers have become much smaller and easier to use. 227 • DNA computers will become more common for solving very complex problems. • Just as DNA cloning and sequencing were once manual tasks, DNA computers will also become automated. In addition to the direct benefits of using DNA computers for performing complex computations, some of the operations of DNA computers already have, and perceivably more will be used in molecular and biochemical research. • Read more at: • http://www.cis.udel.edu/~dna3/DNA/dnacomp.html; http://dna2z.com/dnacpu/dna.html; • • http://www.liacs.nl/home/pier/webPagesDNA; http://www.corninfo.chem.wisc.edu/writings/DNAcomputing.html; http://www.comp.leeds.ac.uk/seth/ar35/ 228 Quantum Computing 229 • Today: fraction of micron (10-6 m) wide logic gates and wires on the surface of silicon chips. • Soon they will yield even smaller parts and inevitably reach a point where logic gates are so small that they are made out of only a handful of atoms. • 1 nm = 10-9 m 230 • On the atomic scale matter obeys the rules of quantum mechanics, which are quite different from the classical rules that determine the properties of conventional logic gates. • So if computers are to become smaller in the future, new, quantum technology must replace or supplement what we have now. 231 What is quantum mechanics? • The deepest theory of physics; the framework within which all other current theories, except the general theory of relativity, are formulated. Some of its features are: • Quantisation (which means that observable quantities do not vary continuously but come in discrete chunks or 'quanta'). This is the one that makes computation, classical or quantum, possible at all. 232 • Interference (which means that the outcome of a quantum process in general depends on all the possible histories of that process). • This is the feature that makes quantum computers qualitatively more powerful than classical ones. 233 • Entanglement (Two spatially separated and non-interacting quantum systems that have interacted in the past may still have some locally inaccessible information in common – information which cannot be accessed in any experiment performed on either of them alone.) • This is the one that makes quantum cryptography possible. 234 • The discovery that quantum physics allows fundamentally new modes of information processing has required the existing theories of computation, information and cryptography to be superseded by their quantum generalisations. 235 • Let us try to reflect a single photon off a half-silvered mirror i.e. a mirror which reflects exactly half of the light which impinges upon it, while the remaining half is transmitted directly through it. • It seems that it would be sensible to say that the photon is either in the transmitted or in the reflected beam with the same probability. 236 • Indeed, if we place two photodetectors behind the half-silvered mirror in direct lines of the two beams, the photon will be registered with the same probability either in the detector 1 or in the detector 2. • Does it really mean that after the half-silvered mirror the photon travels in either reflected or transmitted beam with the same probability 50%? • No, it does not ! In fact the photon takes `two paths at once'. 237 This can be demonstrated by recombining the two beams with the help of two fully silvered mirrors and placing another half-silvered mirror at their meeting point, with two photodectors in direct lines of the two beams. With this set up we can observe a truly amazing quantum interference phenomenon. 238 • If it were merely the case that there were a 50% chance that the photon followed one path and a 50% chance that it followed the other, then we should find a 50% probability that one of the detectors registers the photon and a 50% probability that the other one does. • However, that is not what happens. If the two possible paths are exactly equal in length, then it turns out that there is a 100% probability that the photon reaches the detector 1 and 0% probability that it reaches the other detector 2. Thus the photon is certain to strike the detector 1! 239 It seems inescapable that the photon must, in some sense, have actually travelled both routes at once for if an absorbing screen is placed in the way of either of the two routes, then it becomes equally probable that detector 1 or 2 is reached. 240 • Blocking off one of the paths actually allows detector 2 to be reached. With both routes open, the photon somehow knows that it is not permitted to reach detector 2, so it must have actually felt out both routes. • It is therefore perfectly legitimate to say that between the two halfsilvered mirrors the photon took both the transmitted and the reflected paths. 241 • Using more technical language, we can say that the photon is in a coherent superposition of being in the transmitted beam and in the reflected beam. • In much the same way an atom can be prepared in a superposition of two different electronic states, and in general a quantum two state system, called a quantum bit or a qubit, can be prepared in a superposition of its two logical states 0 and 1. Thus one qubit can encode at a given moment of time both 0 and 1. 242 • In principle we know how to build a quantum computer; we can start with simple quantum logic gates and try to integrate them together into quantum circuits. • A quantum logic gate, like a classical gate, is a very simple computing device that performs one elementary quantum operation, usually on two qubits, in a given period of time. • Of course, quantum logic gates are different from their classical counterparts because they can create and perform operations on quantum superpositions. 243 • So the advantage of quantum computers arises from the way they encode a bit, the fundamental unit of information. • The state of a bit in a classical digital computer is specified by one number, 0 or 1. • An n-bit binary word in a typical computer is accordingly described by a string of n zeros and ones. 244 • A quantum bit, called a qubit, might be represented by an atom in one of two different states, which can also be denoted as 0 or 1. • Two qubits, like two classical bits, can attain four different welldefined states (0 and 0, 0 and 1, 1 and 0, or 1 and 1). 245 • But unlike classical bits, qubits can exist simultaneously as 0 and 1, with the probability for each state given by a numerical coefficient. • Describing a two-qubit quantum computer thus requires four coefficients. In general, n qubits demand 2n numbers, which rapidly becomes a sizable set for larger values of n. 246 • For example, if n equals 50, about 1015 numbers are required to describe all the probabilities for all the possible states of the quantum machine--a number that exceeds the capacity of the largest conventional computer. • A quantum computer promises to be immensely powerful because it can be in multiple states at once (superposition) -- and because it can act on all its possible states simultaneously. • Thus, a quantum computer could naturally perform myriad operations in parallel, using only a single processing unit. 247 • The most famous example of the extra power of a quantum computer is Peter Shor's algorithm for factoring large numbers. • Factoring is an important problem in cryptography; for instance, the security of RSA public key cryptography depends on factoring being a hard problem. • Despite much research, no efficient classical factoring algorithm is known. 248 • However if we keep on putting quantum gates together into circuits we will quickly run into some serious practical problems. • The more interacting qubits are involved the harder it tends to be to engineer the interaction that would display the quantum interference. • Apart from the technical difficulties of working at single-atom and single-photon scales, one of the most important problems is that of preventing the surrounding environment from being affected by the interactions that generate quantum superpositions. 249 • The more components the more likely it is that quantum computation will spread outside the computational unit and will irreversibly dissipate useful information to the environment. • This process is called decoherence. Thus the race is to engineer submicroscopic systems in which qubits interact only with themselves but not not with the environment. 250 But, the problem is not entirely new! Remember STM? (Scanning Tuneling Microscopy ) STM was a Nobel Prize winning invention by Binning and Rohrer at IBM Zurich Laboratory in the early 1980s 251 • Title : Quantum Corral • Media : Iron on Copper (111) 252 • Scientists discovered a new method for confining electrons to artificial structures at the nanometer length scale. • Surface state electrons on Cu(111) were confined to closed structures (corrals) defined by barriers built from Fe adatoms. T • The barriers were assembled by individually positioning Fe adatoms using the tip of a low temperature scanning tunnelling microscope (STM). A circular corral of radius 71.3 Angstrom was constructed in this way out of 48 Fe adatoms. 253 The standing-wave patterns in the local density of states of the Cu(111) surface. These spatial oscillations are quantummechanical interference patterns caused by scattering of the twodimensional electron gas off the Fe adatoms and point defects. 254 What will quantum computers be good at? • The most important applications currently known: • Cryptography: perfectly secure communication. • Searching, especially algorithmic searching (Grover's algorithm). • Factorising large numbers very rapidly • (Shor's algorithm). • Simulating quantum-mechanical systems efficiently 255 What is Computation? • Theoretical Computer Science 317 (2004) • Burgin, M., Super-Recursive Algorithms, Springer Monographs in Computer Science, 2005, ISBN: 0-387-95569-0 • Minds and Machines (1994, 4, 4) “What is Computation?” • Journal of Logic, Language and Information (Volume 12 No 4 2003) What is information? 256 • Theoretical Computer Science, 2004 Volume:317 Three aspects of super-recursive algorithms and hypercomputation or finding issue:1-3 black swans Burgin, Klinger Hypercomputation • Toward a theory of intelligence Kugel • Algorithmic complexity of recursive and inductive algorithms Burgin • Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines Wiedermann • Experience, generations, and limits in machine learning Burgin, Klinger • Hypercomputation with quantum adiabatic processes Kieu • Super-tasks, accelerating Turing machines and uncomputability Shagrir • Natural computation and non-Turing models of computation MacLennan • Continuous-time computation with restricted integration capabilities Campagnolo • The modal argument for hypercomputing minds Bringsjord, Arkoudas • Hypercomputation by definition Wells • The concept of computability Cleland • Uncomputability: the problem of induction internalized Kelly • Hypercomputation: philosophical issues Copeland 257

Descargar
# Document