Browse Prior Art Database

THE APPROXIMATION OF PROBABILISTIC TURING AUTOMATA BY PROBABILISTIC PUSHDOWN AUTOMATA

IP.com Disclosure Number: IPCOM000128356D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 8 page(s) / 24K

Publishing Venue

Software Patent Institute

Related People

Clarence A. Ellis: AUTHOR [+3]

Abstract

The concepts of Probabilistic Pushdown Automata and Probabilistic Tur-ing Automata are defined. Then an algorithm is proposed which allows one to approximate the Turing Automaton by the Pushdown Automaton. The goodness of fit of this approximation is investigated, and an error bound is derived.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 26% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE APPROXIMATION OF PROBABILISTIC TURING AUTOMATA BY PROBABILISTIC PUSHDOWN AUTOMATA

by Clarence A. Ellis

Department of Computer Science University of Colorado Boulder, Colorado Report #CU-CS- 020-73 JUNE, 1973

1

ABSTRACT The concepts of Probabilistic Pushdown Automata and Probabilistic Tur-ing Automata are defined. Then an algorithm is proposed which allows one to approximate the Turing Automaton by the Pushdown Automaton. The goodness of fit of this approximation is investigated, and an error bound is derived. A Probabilistic Pushdown Storage Automaton (called a pushdown P auto- maton) consists of a finite state control unit, two one-way infinite tapes (an input~tape and a storage tape), a read head for the input tape, and a read-write head for the storage tape. The machine operates by changing states at discrete time intervals. Along with this state change, it may read a symbol of the input tape, causing the tape to move left to the next symbol; and it may perform a stack operation (push or pop) on the storage tape. The new state and the string of symbols printed on the storage tape at time t + I depend probabilistically upon the old state and the symbols read on the two tapes at time t. This can be stated formally.

Definition: A Probabilistic Pushdown Storage Automaton A over an alpha- bet, T, of input symbols is a system (Q, M, S, 'E') where Q is a finite set of states,

(Equation Omitted)

is a finite set of storage tape symbols, Is

(Equation Omitted)

is an n-dimensional initial state vector, and M is a probabilistic transition function from

(Equation Omitted)

A situation of A is a triple (q, s, a) with

(Equation Omitted)

is started in the situation

(Equation Omitted)

1 * This work was supported by NSF Grant GJ-660.

University of Colorado Page 1 Dec 31, 1973

Page 2 of 8

THE APPROXIMATION OF PROBABILISTIC TURING AUTOMATA BY PROBABILISTIC PUSHDOWN AUTOMATA

where

(Equation Omitted)

, and a 0 is the first symbol (not including #) of some string

(Equation Omitted)

which is present on the input tape.

A Pictorially, A has the following initial configuration, where the # denotes a blank square of a tape.

>-3-

Then using the terminology of Haines

(Equation Omitted)

will be written as

(Equation Omitted)

where p is the probability associated with the transi-tion. Only three types of instructions are allowed:

(Equation Omitted)

This means if the automaton is in the state q, and scanning symbols s and a i on the storage and input tapes respectively, then with probability p, a transition into state q' will occur, and the storage and input tapes will move one-square to the left and then s' e S - {#I will be printed on the storage tape one square to the right of s.

(Equation Omitted)

implies the storage tape is left unchanged and unmoved, so

(Equation Omitted)

The next situation is

(Equation Omitted)

assum-ing

(Equation Omitted)

where the input string is

(Equation Omitted)

Unive...