Michael Pilat

Bio [2006]
Michael recently graduated from the University of Chicago with a master's degree in computer science, and holds a a bachelor's degree in mathematics and computer science from the University of Illinois at Urbana-Champaign. He has never been too far away from a computer since his first experiences playing Zaxxon on an Apple IIc. He joined Wolfram Research in 2003, and is currently a senior software engineer in the Software Technology department, where he carefully hand-crafts Mathematica technology with only the highest-quality ones and zeros. He has developed features for Mathematica 5.1 and 5.2, as well as future versions, and the WolframTones project. He currently has 20 open bugs filed against him, but is confident he will be acquitted.

Project Title
Optimizing Turing Machine Computations

Project
My project will study Turing machine computations, and specifically what techniques can be applied to predict, optimize, or compress them. I will initially focus on one-dimensional machines of limited color in order to develop a solid base on which to build more complex operations.

Diagram of the q-2 k-5 universal machine from p. 707 of A New Kind of Science

There are many potential optimizations for Turing computations:

State Pruning

States that are never reached by any computation path can be removed. Similarly, states that only serve to move the head position but never change the tape contents could be eliminated and the "calling" state re-written as a multi-position move.

Periodic Behavior

Does a machine exhibit periodic behavior? If so, is such behavior bounded in space? Can periodic behavior be detected and proved? For example, if a Turing machine has visited all possible states with all possible input colors, and never walked out of some bounded tape region, it will never leave that tape region. This is a useful fact to know, because in a Turing machine emulator one can then assume that the tape will never need to grow wider. If a machine exhibits predictable periodic behavior, it becomes unnecessary to continue computing it after the periodic behavior is determined. The output could even be compressed into a periodic notation, much like pointer compression for rational numbers.

Maximum Excursions

Does the sequence of maximum head excursions ever form an arithmetic sequence? What about other sequences of head positions? Even if the sequence of maximum excursions is a well-behaved sequence, non-trivial things could still happen in between.

Alternate Forms

When is it possible to write the output or total state of a Turing machine as a parameter of time? What about symbolic input? Could Turing computations be built up as a nested structure of symbolic operations? When is it possible to find an analytical form for the function computed by a Turing machine? When can this be accomplished algorithmically?

To support these efforts, I plan to develop functionality to help visualize Turing machine state machines, as well as practical optimizations that could be applied to Mathematica's new TuringMachine function to make computation more efficient.

Favorite Four-Color, Radius-1/2 Rule
Rule chosen: 414256860