On pebble automata (Q1088408)

Steinchen (pebbles) heißen hier sehr bildhaft reversible und kumulierbare Markierungen, die eine Turing-Maschine (TM) auf ihrem Eingabeband anbringen und aufsuchen kann. 1-Steinchen-TM können Probleme in DSPACE(loglog n) bearbeiten; laut \textit{A. R. Freedman} und \textit{R. E. Ladner} [J. Comput. Syst. Sci. 11, 118-128 (1975; Zbl 0307.68036)] ist diese Problemklasse für TM ohne Steinchen verschlossen. Arbeitsplatz unterhalb loglog n ist für 1 Steinchen äquivalent zu konstantem Arbeitsplatz. 2-Steinchen-TM ohne Arbeitsband akzeptieren dieselben Sprachen wie Automaten mit nichtlöschbarem, aber zerstörungsfrei lesbarem Keller. 3-Steinchen-TM ohne Arbeitsband akzeptieren dieselben Sprachen wie 2weg-Kellerautomaten (2DPDA's). Wesentlicher als die Fülle von Einzelergebnissen, die sichtlich der ordnenden Hand des Morphologen (Zwicky) bedürfen, ist die breite Anwendung einer Beweistechnik, die sich der Tiefensuche über dem Baum der Konfigurationen eines deterministischen Automaten bedient [\textit{M. Sipser}, Theor. Comput. Sci. 10, 335-338 (1980; Zbl 0423.68011)].