skip to main content

H.B. Keller Colloquium

Monday, March 3, 2025
4:00pm to 5:00pm
Add to Cal
Annenberg 105
A Reliable Turing Machine
Peter Gacs, Professor Emeritus, Computer Science Department, Boston University,

We consider a computation model that is like a 1-tape Turing machine.  It has an
internal state (from a fixed finite set), and a head scanning a tape with cells
having content from some finite alphabet.  In each step the head can move at
most one step, and the state and the content of the scanned cell can change.
This change is dictated by a fixed transition function in most cases.  But in
difference from a standard Turing machine, with some small probability and
independently in each time step, the change can be something else (it still must
be local!). 
The result (joint work with Ilir Çapuni) is that there is a machine of this kind that,
that for some positive noise bound, performs arbitrarily large computations. 
(We will spell out the precise input-output conventions.)
The construction and the proof are complex, similar to the hierarchical one used
for reliable cellular automata, but we don't know of any easy reduction from one
result to the other.

For more information, please contact Narin Seraydarian by phone at (626) 395-6580 or by email at [email protected].