ACM A.M. TURING CENTENARY CELEBRATION: JUNE 15 & 16, 2012
PALACE HOTEL, SAN FRANCISCO, CA

Talks by these A.M. Turing laureates:

  1. Edmund Clarke, "Computable Real Numbers and Why They Are Still Important Today"
    Abstract
    Although every undergraduate in computer science learns about Turing Machines, it is not well known that they were originally proposed as a means of characterizing computable real numbers. For a long time, formal verification paid little attention to computational applications that involve the manipulation of continuous quantities, even though such applications are ubiquitous. In recent years, however, there has been great interest in safety-critical hybrid systems involving both discrete and continuous behaviors, including autonomous automotive and aerospace applications, medical devices of various sorts, control programs for electric power plants, and so on. As a result, the formal analysis of numerical computation can no longer be ignored. This talk focuses on one of the most successful verification techniques, temporal logic model checking. Current industrial model checkers do not scale to handle realistic hybrid systems. The key to handling more complex systems is to make better use of the theory of the computable reals, and computable analysis more generally. New formal methods for hybrid systems should combine existing discrete methods in model checking with new algorithms based on computable analysis. In particular, this talk discusses a model checker currently being developed along these lines.
  2. Alan C. Kay, "Extracting Energy from the Turing Tarpit"
    Abstract
    Part of Turing's fame and inspiration came from showing how a simple computer can simulate every other computer, and so “anything is possible”. The “Turing Tarpit” is getting caught by “anything is possible but nothing is easy”. One way to get caught is to stay close to the underlying machine with our languages so that things seem comprehensible in the small but the code blows up into intractable millions of lines. What if we used “anything is possible” to make very different kinds of computers which require new learning but the code compactly fits the problem and stays small?
  3. Butler Lampson, "What Computers Do: Model, Connect, and Engage"
    Abstract
    Every 30 years there is a new wave of things that computers do. Around 1950 they began to model events in the world (simulation), and around 1980 to connect people (communication). Since 2010 they have begun to engage with the physical world in a non-trivial way (embodiment—giving them bodies). Today there are sensor networks like the Inrix traffic information system, robots like the Roomba vacuum cleaner, and cameras that can pick out faces and even smiles. But these are just the beginning. In a few years we will have cars that drive themselves, glasses that overlay the person you are looking at with their name and contact information, telepresence systems that make most business travel unnecessary, and other applications as yet unimagined. All computer systems are built on the physical foundation of hardware (steadily improving, according to Moore's law) and the intellectual foundations of algorithms, abstraction and probability. Their performance is determined by basic issues of latency, bandwidth, availability and complexity. In the future they will deal with uncertainty much better than today, and many of them will be safety-critical and hence much more dependable.
  4. Dana S. Scott, "Lambda Calculus Then and Now" λ–Calculus Timeline
    Abstract
    A very fast development in the early 1930s, following Hilbert's codification of Mathematical Logic, led to the Incompleteness Theorems, Computable Functions, Undecidability Theorems, and the general formulation of recursive Function Theory. The so-called Lambda Calculus played a key role. The history of these developments will be traced, and the much later place of Lambda Calculus in Mathematics and Programming-Language Theory will be outlined.

Panels by past ACM A.M. Turing Award winners:

  1. Turing the Man
    Chair: Keith Van Rijsbergen
    Panel: Charles Bachman, Calvin Gotlieb, William Newman, Wendy Hall
    Abstract
    The panelists will discuss Alan Turing and Sara Turing, his mother, based on the personal experiences of the panelists. William Newman will recount amusing incidents during the time Turing was a regular visitor at the Newman home. Kelly Gotlieb will describe his meetings with Turing at Manchester University during the early 1950s. Charlie Bachman and his wife met with Sara Turing in the mid-1970s, and Charlie will give an account of that meeting. Finally, Wendy Hall will describe the Turing Archive project in the UK and the Turing exhibition in the London Science Museum.
  2. Human and Machine Intelligence
    Chair: Barbara Grosz
    Panel: Edward A. Feigenbaum, Marvin Minsky, Judea Pearl, Raj Reddy
    Abstract
    In his 1950 Mind paper, Alan Turing reframed the question of whether machines could think as an operational or behavioral question: Could a computer be built that was indistinguishable from people in playing the “imitation game,” now known as “the Turing Test”? He conjectured that by the end of the 20th century “one [would] be able to speak of machines thinking without expecting to be contradicted” and that computers would succeed in the Turing Test. Turing's fi rst conjecture proved right. Although his second has not yet been realized, research in Artifi cial Intelligence (AI) has generated a variety of algorithms and techniques regularly deployed in systems enabling them to behave in ways that are broadly considered to be intelligent. The performances of Watson, Siri, and driverless cars are but a few examples in the public eye. This session's panelists will highlight some of the major accomplishments of research in AI and its infl uential role in the development of computer science and computer systems more broadly, considering not only progress in individual subfi elds, but also designs for integrating these into well-functioning systems. They will also consider the ways in which AI theories and methods have influenced research on human cognition in behavioral sciences and neuroscience as well as scientific research more generally, and they will discuss major challenges and opportunities for the decades ahead.
  3. The Turing Computational Model
    Chair: Moshe Vardi
    Panel: Stephen Cook, Juris Hartmanis, William Kahan, Richard E. Stearns
    Abstract
    The panel presentations will discuss the beauty and simplicity of the Turing machine formulation of the previously elusive concept of computability and the intuitively satisfying explanation of the power and limitations of computability. They will also review how the Turing machine model provided simple proofs of deep results in logic, including gödel's incompleteness theorem. The panel will also examine specific results in computer science infl uenced by the Turing machine model as well as how it shaped the development of computational complexity theory. Quantum computing will be discussed and its relationship to the classic Turing machine model. The panel will also discuss what Alan Turing might say about the Inevitable Fallibility of Software.
  4. Information, Data, Security in a Networked Future
    Chair: Vint Cerf
    Panel: John Hopcroft, Bob Kahn, Ron Rivest, Adi Shamir
    Abstract
    The digital information revolution begins as giants such as Alan Turing, Claude Shannon and John von neumann, among many others, recognize the power of digital representations and programmable computers. Although rooted in the technology of his time, Vannevar Bush's portrait of the information revolution has emerged and flourished especially in the form of the World Wide Web resting atop the global Internet.
    The panelists will explore some specifics of the digital information revolution, notably theory and practice in securing, authenticating and maintaining the integrity of information (Cerf); and roots of modern cryptography and current topics in this area (rivest and Shamir). They will also gain insight into the long-term problem of identifying, fi nding, and assuring the integrity of digital objects in the most general sense of that term (Kahn). Finally, they look at how our understanding of computer science is changing (Hopcroft) and how that evolution will affect the digital world in which are we spending an increasing fraction of our daily lives.
  5. Programming Languages – Past Achievements and Future Challenges
    Chair: Susan Graham
    Panel: Frances Allen, Barbara Liskov, Nicklaus Wirth
    Abstract
    The design of programming languages and their compile-time and run-time implementation are closely related, and are dependent on the underlying computational model. In the 1960s, 70s, and 80s many languages were designed, and many implementation strategies and computational models were explored. Since then, the commercial world has largely settled on a few legacy languages. Meanwhile, both the capabilities of computing systems and the ways in which they are used have changed dramatically. The panelists will summarize the lessons they have learned about language design, and also what has not been learned. They will consider how those lessons can be applied to the myriad application domains, architectural frameworks, user needs, and economic considerations that exist today, and will speculate about the future.
  6. Computer Architecture
    Chair: David Patterson
    Panel: Frederick P. Brooks, Jr., Ivan Sutherland, Charles P. (Chuck) Thacker
    Abstract
    Sixty-five years ago, Alan Turing produced a proposal for the construction of a general-purpose computer, the Automatic Computing Engine, or ACE. Subsequently built at the U.K. National Physical Laboratory, it was briefly the fastest computer in the world. Although its architecture was quite different from the arrangement proposed by Von Neumann and others that eventually came to dominate the computing landscape, examining it gives us a chance to understand some of the tradeoffs that early computer architects explored.
    The panel will examine the ACE to provide a setting for the discussions that follow, in which they will explore some of the architectural tradeoffs that have been made in the past, are still being made today, and which will shape the direction of computing in the future. What would Alan Turing have thought about the impact that computers have had on society? What would he have thought about the warehouse-scale computing that makes possible a realization of Vannevar Bush's 1945 Memex vision? What about the possibility of quantum computing? The panelists will discuss these topics as well as the progress and future of academic computer architecture research.
  7. Systems Architecture, Design, Engineering, and Verification - The Practice in Research and Research in Practice
    Chair: Dahlia Malkhi
    Panel: Fernando J. Corbato, E. Allen Emerson, Joseph Sifakis, Ken Thompson
    Abstract
    More than any other area in computer science, the interaction and boundary between science and engineering is blurred in the systems area, with cross fertilization from both directions. The systems panel will explore the past, present and future relationship between systems research and engineering practice.
    Panel members will review their past award-winning research in perspective, and describe its impact on the computing world.
    They will discuss the relationship between systems research and engineering practices: when does systems innovation emanating from industry become an invention and when does academic research stop being science and become engineering? How does practice-driven research impact the real world and how does the real world reflect back on foundations? In what forms does technology create research challenges, and in what manner does applied research give solid base for development?
    They will surmise about the future of systems research: What are the fundamental challenges posed by the scale of today's cloud computing systems and mega-size data centers? How to organize software of large-scale distributed executions or mega-ton lines of code? What new opportunities are enabled by novel technologies like flash memory and transactional memory? How to integrate hand-in-hand design of software and architecture?
  8. An Algorithmic View of the Universe
    Chair: Christos Papadimitriou
    Panel: Leonard Adleman, Richard M. Karp, Donald E. Knuth, Robert Tarjan, Leslie G. Valiant
    Abstract
    In the years since Alan Turing, and following his lead, computer scientists advanced their understanding of computational phenomena by developing a very specialized, original and penetrating way of rigorous thinking. Now it turns out that this “algorithmic” way of thinking can be applied productively to the study of important phenomena outside computation proper (examples: the cell, the brain, the market, the universe, indeed mathematical truth itself). This development is an exquisite unintended consequence of the fact that there is latent computation underlying each of these phenomena, or the ways in which science studies them.

Film by Patrick Sammon:

  1. "Codebreaker"
    A special preview screening in the Gold Ballroom of Patrick Sammon’s new film about Alan Turing’s heroic life, tragic death, and lasting legacy. This drama documentary will be released later this year in the U.S. Don’t miss the chance to get a sneak peek at this powerful fi lm. Patrick Sammon, executive producer and creator, will provide an introduction before the screening.

    If you are interested in scheduling an academic or corporate screening of this film, please email Patrick at [email protected].

Official Program

Follow us for updates: Facebook  Twitter  LinkedIn  #ACMTuring100