2007 | OriginalPaper | Buchkapitel
Unconventional “Stateless” Turing–Like Machines
verfasst von : Joshua J. Arulanandham
Erschienen in: Unconventional Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We refer to Turing machines (TMs) with only one state as “stateless” TMs. These machines remain in the same state throughout the computation. The only way they can “remember” anything is by writing on their tapes. Stateless TMs have limited computing power: They cannot compute all computable functions. However, this handicap of a stateless TM can be overcome if we modify the TM a little by adding an extra feature. We propose a modified Turing–like machine called a JTM—it is stateless (has only one internal state) by definition—and show that
it is as powerful as any TM
. That is, a JTM does not switch states, and yet can compute all computable functions. JTMs differ from conventional TMs in the following way: The tape head spans three consecutive cells on the tape; it can read/write a
string
of three (tape) symbols all at once. However, the movement of the head is not in terms of “blocks of three cells”: in the next move, the head does not “jump” to the adjacent (entirely new) block of three cells; it only
shifts
itself by one cell—to the right or to the left. A JTM is more than a product of theoretical curiosity: it can serve as a “normal form” and might lead to simpler proofs for certain theorems in computation theory.