Two-dimensional grid grammars
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Gene Wall Moore (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
- Advisor
- Michael Willett
Abstract: Everyone has an intuitive understanding of the concept of an algorithm. It is generally agreed that an algorithm, or effective procedure, is a finite set of instructions which meet certain requirements. All instructions must be unambiguous and must not involve any element of chance. Each instruction must be executed in a finite amount of time. It is usually not required that algorithms halt. Instead, the set of instructions must be so specifically stated that any two people executing them would perform precisely the same operations. In this thesis we first introduce a class of mathematical machines which are used to define the concept of an algorithmic computation. These Turing machines [3], which operate on one-dimensional tapes, are defined in Chapter II. We consider machines as computational devices, function evaluators, and acceptor automata for syntactically correct input. A set of instructions, called the Wang programming language, which can be assembled in such a way as to simulate a given Turing machine, is presented in Chapter III. In Chapter IV we define grammars, which are systems for generating strings of symbols with certain structured properties. The Chomsky Hierarchy of classes of restricted grammars is outlined [1]. In Chapter V we introduce a class of machines which operate in a manner similar to Turing machines but on a two-dimensional tape. We refer to this class of machines as grid machines.
Two-dimensional grid grammars
PDF (Portable Document Format)
6798 KB
Created on 1/1/1977
Views: 246
Additional Information
- Publication
- Thesis
- Language: English
- Date: 1977
- Subjects
- Numerical grid generation (Numerical analysis)
- Turing machines
- Algorithms