Why I Think About Turing Machines

Tim Menzies
tim@menzies.us
April 5, 2008
A presentation to the NSF CODEWORKS workshop

Introduction

CS and UI is the art of building glass walls to hide users from the computational cliff. Hopefully, most users are blind to how narrow is their treacherous path. But without the language of the Turing machine, you are blind to certain restrictions to writing, unable to explain why your system is broken, unable to avoid that problem in the fture.

But what is a Turing machine?

http://rendell-attic.org/gol/tm.htm

Should we talk about them? Hell, yes. Otherwise, we are blind to something that really matters.

"Keep the pen moving. Editing stfiles creativity. you can always go over something later to fix the spelings and gramer grammer."

And, as a computer scientist, I would add the language must generate sentences that runs and runs fast. Brian Sower's work with the gaming industry taught me the vital importance of striving to write what runs fast (so I disagree with Alan: we write with consequences and there are some consequences I want to avoid).

• Without Turing machines, I can't promise you that since I become blind to an essential dimension to computational problems.

So here's an example of language blinding its users to an essential dimension in a problem. Bees on returning to the hive must report where they've been. In response to "Where's the honey, honey?", they do a little dance.

If the honey is on top of a tower, and one bee lucks onto it, then a little while later you'll find bees buzzing round the foot of the tower, puzzled. If they ask "where's that honey, honey?" there is no answer because their language makes them blind to an essentional feature of the problem, namely the third dimension. The problem is that the bee's dance gives clues to the direction of the honey, how good it is, and how far away it is but not the height.

So what's my point? Well, stay with me here. Begin lecture on comptuational complexity.

Complexity and Turing Machines

Moore's Law is not enough. There are many problems facing us that laugh in the face of the Moore's tiny sky slope.

(Notes from Scott Aaronson:)

• P: Problems that are solvable by polynomial-time algorithms
• We just don't know if many problems are in P:
  • Given a map, can every country be colored red, green, or blue so that no neighboring countries are colored the same?
  • Given a collection of boxes, can they be packed in your trunk?
  • Given a collection of cities, together with the distances between them, is there a route of at most 10,000 miles that visits every city once?
  • Given a Boolean formula, is there a setting of the variables that makes it true?
• Now P belongs to a bigger class of problems called NP, for Nondeterministic Polynomial-Time. A problem is in NP if, whenever the answer is "yes," you can check that answer in polynomial time.
• Note that it can be very hard to generate that that answer. Did the Russians get a satellite in orbit? Yes- go look in the sky. How can we do it? Massively hard problem to solve.
• We say a problem is NP-hard if any NP problem can be efficiently reduced to it -- in other words, if there's a polynomial-time algorithm that translates any instance of an NP problem into an instance of the problem in question. Then a problem is called NP-complete if it's both NP-hard and in NP. In other words, NP-complete problems are "the hardest problems in NP."
• The big discovery that really got the field started, in the early seventies, is that not just one or two but thousands of natural search problems are NP-complete. Computer science has a row of dominoes of problems mapped into other problems mapped into other problems.
• At at the end of the line, is a Turing machine. Stephen Cook, in his 1971 paper "The Complexity of Theorem Proving Procedures", mapped a simple logic problem (3SAT) to a turing machine.
• So for example, the map-coloring, box-packing, Traveling Salesman, and Boolean satisfiability problems are all NP-complete. This means that an efficient solution to any one of them would imply efficient solutions to all the rest: if you find a way to color maps, then you've also found a way to pack boxes in your trunk, and so on. In a very precise sense, all these problems are just different encodings of the same thing.

So What?

It turns out that seemingly minor changes to a problem, to the language we allow when writing knowledge, can be catestrophic since it throws you out of P and into very slow NP-hard. For example "Applications of Abduction: Testing Very Long Qualitative Simulations" by T.J. Menzies and R.F. Cohen and S. Waugh and S. Goss. IEEE Transactions of Data and Knowledge Engineering pages 1362-1375 November/December 2003 . Available from http://menzies.us/pdf/97iedge.pdf.

• Consider the seemingly simple statement:
  • "A increases B"
• Sounds simple enough. But do you mean:
  1. A going up makes B goes up; e.g. pouring coffee into a cup
  2. A going down makes B goes down
  3. 1 + 2; e.g. linear proportionality
  It turns out #3 has the propery that for two-state devices (more, less) then every upstream state comments on every downstream state. So a causal model that only supports #3 saturates
  • If you can't reach some downstream state in two time ticks...
  • ... you can never get there at all
• Which means that #3 lets us reasoning about infinite interactions infintely far into the future (because the future is closer than you think).
• But #1 does not. So if you really want to predict the future, #3 is safe and #1 implies a limit to how much coffee your characters can drink.

That's one example. There are many more.

The Lesson

So, the language not only needs to work, but it must generate sentences that runs and runs fast. knowledge of the Turing machine informs what you can't say such that:

• you can say the rest faster (faster inference)
• you can say more (scalability)

So, we not only write, but we write what we hope will run. As a computer scientist, I want to give you a keyboard / environment where chapter1 runs as fast as chapters 1 to 100. But you have to let me tape over some of the keys.

Now, how successfully have I explained thirty years of computational theory? Are you still a blind bee, unaware of dimensions that limit the execution of your creations? Or will you know watch for those computational cliffs / limits to expression, and exploit them?

This work is licensed under a
Creative Commons Attribution-Noncommercial 3.0 United States License.