Browse Prior Art Database

TWO-DIMENSIONAL TURING MACHINES WITH UNINITIALIZED WORKSPACES

IP.com Disclosure Number: IPCOM000148286D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12

Publishing Venue

Software Patent Institute

Related People

Melville, Robert: AUTHOR [+2]

Abstract

TWO-DIMENSIONAL TURP.NG MACIIINES WII?l UNINITIALIZD WORKSPACES Robert Melville Department of Computer Science Cornel7 UniversityIthaca, New York 14853 Two-dimension3 1 Turing lhch ines with uninitialized workspaces The coilvent ionzl tvo-dimensional Tf.1 model[l~U] provides an infinite two-dimensional workspace assumed to be blank a t the start of the computation. In other words, the machine assumes that any cell* not previously visited i n a conputation, contains some distinguished symbol b, an element of the workplzne alphabet. As an example of a computation making essential use of this assumptions consider the two dimensional self-crossing problem. The machine processes on-line an input sequence over the alphabet {N,S,E,!J). Interpreting each symbol a s a unit step in the corresponding compass direction, the machine must report whecever the path so described "crosses" itself, i.e. when the current endpoint of the path coiccides with some previous point of the psth. A solution by a two dimensional l24 is easy if we assume the workplane to be blank initic?lly. The input alphabet of the machine is {N~S,E,W] and the workplane alphabet is {bsl). The machine reads input symbols 2nd moves i t s head accordi.ngly. If a move is to a blank cell, the machine prints a 1; if the move is to a cell containing a 1, the machine reports a self-crossing. The time to process n input symbols is clearly o(R)*

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 26% of the total text.

Page 1 of 14

TWO-DIMENSIONAL TURP.NG MACIIINES WII?l UNINITIALIZD WORKSPACES

Robert Melville

Department of Computer Science Cornel7 University
Ithaca, New York 14853

[This page contains 1 picture or other non-text object]

Page 2 of 14

[This page contains 1 picture or other non-text object]

Page 3 of 14

Two-dimension3 1 Turing lhch ines with uninitialized workspaces

    The coilvent ionzl tvo-dimensional Tf.1 model[l~U] provides an infinite two-dimensional workspace assumed to be blank a t the start of the computation. In other words, the machine assumes that any cell* not previously visited i n a conputation, contains some distinguished symbol b, an element of the workplzne alphabet. As an example of a computation making essential use of this assumptions consider the two dimensional self-crossing problem. The machine processes on-line an input sequence over the alphabet {N,S,E,!J). Interpreting each symbol a s a unit step in the corresponding compass direction, the machine must report whecever the path so described "crosses" itself, i.e. when the current endpoint of the path coiccides with some previous point of the psth.

    A solution by a two dimensional l24 is easy if we assume the workplane to be blank initic?lly. The input alphabet of the machine is {N~S,E,W] and the workplane alphabet is {bsl). The machine reads input symbols 2nd moves i t s head accordi.ngly. If a move is to a blank cell, the machine prints a 1; if the move is to a cell containing a 1, the machine reports a self-crossing. The time to process n input symbols is clearly o(R)*

    In this paper we criticize the above solution as being rather cheap - at least it is not quite f a i r to assign this nlgaritlm only linear running tiine. Suppose the sequrnce of the f i r s t n/2 input symbols is (NE)"'~. The machine records a pat11 3s in figure 1. The scc~nd half of the input could cause a

2

sclf-crossing a t any of tl~c O(n cclls inside the dotted square* so these cells must be i n i t i311y bl ank. A physical Jcvicc haplcuirrnting two-dic~cnsional

- 1

L-lkQlAxl w

[This page contains 1 picture or other non-text object]

Page 4 of 14

storage would have to initialize these cells to blanlc before they arc visited. This observation casts sorltc doubt on the linear running timc of the siraplc

solution given above.

    \nlc propose a more realistic model for multi-dirnensiol.ral Ttl storage: a cell of the work space, not previously visited during the cm~putation, Giay contein any symbol from the workspace a1 phabet. This stipulation invalida tcs the simple solution to the self-crossing problm since the machine could r.ow

get confused readifig spurious 1 's.

    If a (multi-dimensional) Turing Plachine M reading input data I preforcs exactly the same ca:lputetion on I. for any i n i t i a l contents of i t s workspace, ire say the nachine is initialization-independent. The constructio...