ACM Turing Centenary Celebration, Raw Notes

Here is a raw transcript of my hand-written notes from the ACM Turing Centenary Celebration in San Francisco a couple of weeks ago.

Please note that these are my thoughts and impressions, not necessarily those of the speakers, and that it is quite possible that I misheard or misunderstood a few things, or that I incorrectly attributed the wrong person. If you think I made a mistake, please let me know.

Turing, the Man

  • Turing was misunderstood and discriminated against. Who are the misfits now? Who should be supported?
  • Turing’s mom thought the Turing Award maybe was an award given to long-distance runners. Turing was a runner.
  • Apparently, none of the 32 Turing award laureates in the audience knew of Turing when they did their award-winning work? That is hard to believe. Knuth said he knew of Turing. Maybe I misunderstood the question.
  • Knuth: Turing was the first person with the mind of a geek.
  • Turing did things from first principles. That’s why Turing machines are more understandable than Church’s lambda calculus (says Dana Scott).

Human and Machine Intelligence

  • Jim Gray: AI should speak like a native speaker, hear like a native speaker, and see like a person.
  • Interesting definition: all humans can do that. But is this harder than playing chess or proving theorems? Interestingly, it is harder. The easy things are hard.
  • Turing: We should build a “child machine” and educate it.
  • Book: Human Problem Solving
  • Emotions used to re-prioritize goals in multi-agent systems: agents behave better with emotions when there is a lot of uncertainty.
  • Much human intelligence is stored, with fast recognition.
  • Another reference to “Thinking Fast and Slow”.
  • Raj Reddy: “When you have learned something, you store it so you can retrieve it instantly. You dedicate permanent memory to it.” Then why do we forget?
  • Creativity: Brilliant move in Deep Blue vs. Kasparov, game 3. (look up)

What Computers Do: Model, Connect, and Engage

  • Big data: physics, chemistry, biology, geology, social networks.
  • But how much of the data is actually useful? “We only use 10% of our brains” myth, “We only use 10% of our bandwidth”.
  • Connectivity, ubiquity, scaling, approximation, AI, reusable components, dependability, uncertainty: key concepts.
  • Probability distributions, parameterized over the main, like lists, as standard data type?
  • Catastrophe mode – few dependencies on a “catastrophe computing base”, similar to trusted computing base. Make tough choices, but keep your service going.
  • Swap people between security and attackers is a good idea.
  • Butler Lampson: “A new TCP connection for every mouse click? Madness!”

Systems Architecture, Design, Engineering, and Verification – The Practice in Research and Research in Practice

  • Would Turing machines have had the same impact if it had many instructions as opposed to just a few, elegant ones?
  • Biggest advances since Turing: operating systems, programming languages, networks.
  • Future? Not so rosy, says Thompson.
  • 50s: computers were accessible
  • 60s: had become inaccessible because of economic concerns and batch computing
  • Formal verification: Turing 49 paper, “Checking a Large Routine”
  • What makes research practical?
    • Thompson: right people, right time
    • synergism, backing the right people, not just concrete goals
  • “Nice theory symptom” – we often like a nice theory, ignore practical problems and needs
  • Most software (e.g. incrementally written software) is difficult to verify.
  • Airbus software is completely verifiable by design/

Extracting Energy from the Turing Tarpit

  • 67% of fossil fuels are burned to create electricity.
  • Think of our real goal. We don’t want to create electricity, we want to do something with it. Similarly: our goal is not to write millions of lines of code.
  • Alan Kay: “The easiest way to predict the future is to prevent it.” – Lots of things that barely scaled when they were invented are still around and still do not scale.

The Turing Computational Model

  • Widening gap between users and programmers. Users’ expectation and programmers accomplishments.
  • 1960s customs are a source of bugs. We don’t see them as just customs, though, we see them more as “laws”.
  • LSPACE \subset P \stackrel{?}{\subset} NP \stackrel{?}{\subset}  PSPACE
  • LSPACE \subset PSPACE \; \Rightarrow \; (P \subset NP) \; or \; (NP \subset PSPACE)
  • Big-oh does generally not take into account communication costs. What if communication costs become dominant, or if it can break down?
  • Vivek Sarkar: “What about energy? It seems like the Turing model is good to account for energy, as it takes energy to move the tape.

Computer Architecture

  • Sutherland: communication dominates logic in hardware; we must begin to use clock-free designs.
  • Fred Brooks: Turing’s ACE Pilot architecture assumed hardware is expensive and dear, and programmers are abundant and cheap.
  • Chuck Thacker: “Cutting it [knowledge about the way computers work] off at the C computer level seems limiting.”

Programming Languages – Past Achievements and Future Challenges

  • Nicklaus Wirth: “We don’t teach programming anymore. Students come to university already knowing it.” Really? IT seems like he is talking about wasteful programming.
  • Liskov:
    • programming methodology first; then maybe find some programming language features that help.
    • Software architects: “Settle on a simple memory model. If all we can do is put in fences because we can’t reason about it, we haven’t achieved much.”
    • We now teach with Python. We may create a generation of programmers who don’t understand the importance of modularity.
  • Wirth: “Vicious cycle between language used in academia and industry; can only be broken at the university.”

An Algorithmic View of the Universe

  • Valiant (?): Turing pointed out “cultural search”, how science progresses.
  • CS undergrads not interested in natural science applications. Should there be an explicit unit that introduces them to science applications?
  • Karp:
    • “In biology, form is function. Protein folding determines what the protein does.”
    • X-ray crystallography vs. computed folding:
    • Computed folding is computation; therefore, X-ray crystallography is too.
    • Figuring out folding is NP-complete ==> X-ray crystallography is NP-complete
    • How long will it take for a protein to fold? CS can tell biologists: exponential time!
  • Adleman:
    • Learned a lot about being a computer scientist in another field. Biologists don’t talk our language. It’s easy to solve the wrong problem.
    • Biologists may want a sample of not-quite-optimal solutions, but faster.
    • CS can contribute a lot with its “algorithmic lens,” but we need to meet with our “customers.”
  • Tarjan: learn with skepticism, challenge your instructors and the papers you read — that’s where you’ll find problems to solve.
  • Union set: O(inverse Ackerman) – crazy but true
  • Can another Turing come along? “Yes. It’s not so important to know everything, but to have the ability to understand everything.” And perhaps to know of everything.
  • Favorite algorithms: Shrinking blossoms algorithm (look up)
  • Hungarian algorithm for assignment problem
  • Is the strong Turing thesis enough to preclude time travel?
  • Least favorite algorithms: Adleman, genetic algorithms. “We don’t understand the problem, so we hope the computer will understand.” Genetic algorithm idea taken from biology; why assume that the problem space is the same? But if it works (well enough)? Who says genetics in biology (mutation, sexual reproduction) is the best way to evolve?

Information, Data, Security in a Networked Future

  • Shamir: “Codebreakers at Blethley Park not a victory of human brilliance over machines, but a victory of machine power (exhaustive search) over human stupidity (Enigma operator mistakes).”
  • Rivest: “Calling a string ‘secret key’ does not make it secret.”
  • Maybe we need an attitude adjustment: secret keys are secret most of the time. Users don’t make errors most of the time. That helps recover.
  • Many security problems are caused by human error. What can technology do to make humans more trustworthy and compliant?
  • Privacy/trust in social networks: needs to be an open architecture.

Again, these are my notes. In particular, all mistakes are mine. Caveat lector.


About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply