Complex Systems

n-Skip Turing Machines Download PDF

Wiktor K. Macura
Electronic mail address: wmacur1@umbc.edu
Department of Mathematics and Statistics,
University of Maryland, Baltimore County,
Baltimore, Maryland, 21228

Abstract

A Turing Machine's head is limited to moving one cell in either direction on the tape for a given iteration. We investigate a form of Turing Machine where the head is allowed to move n cells in either direction. We find that such Turing Machines, named n-Skip Turing Machines, are capable of exhibiting complex behavior for simple initial conditions with two states and two colors.