Graduate Thesis Or Dissertation
 

Computation by a Turing machine carried out in a Minsky post tag formalism

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/5t34sn25f

Descriptions

Attribute NameValues
Creator
Abstract
  • This thesis documents a method of proving that Turing machines work for every case, if the construction of the Turing machine is known. Mathematical Induction is used to construct the proof that the Turing machine for binary addition will work in every well-formed case of the input that it receives. This proof can serve as a general model for proving that Turing machines work if their constructions are known and provided they do work. The modification of a Turing machine for binary addition (TBA) in alphabet A: {S, 1, 0, +, a, b, c,} was investigated. The alphabet was transformed and the machine modified so that it could perform the same operations in a new alphabet Z: {I,S}. Each element of alphabet A is represented by a three member string of occurrences of elements of alphabet Z. A cycle to recognize, write and move is needed for this modification of TBA. An increased number of subsidiary states is required. For each cycle within a quintuple for alphabet A, the number of subsidiary states for TBA to function in alphabet Z equals to the square of the number of occurrences of elements in Z that represent an element of alphabet A. It was shown that the modified TBA could perform the same operation as the original TBA. Complete configurations for each state of a Turing machine can be reconstructed from a number, a labelled number related to a complete configuration of a Turing machine operating in the alphabet Z on a tape with a marked left end. This construction illustrates the claim of Marvin Minsky that the Post-tag algorithm can simulate a Turing machine.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details HenryCalvinOscar1975.pdf 2017-08-14 Public Download