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

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/5t34sn25f

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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 Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
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
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-11-20T02:30:55Z (GMT) No. of bitstreams: 1 HenryCalvinOscar1975.pdf: 679526 bytes, checksum: eb0250878b29f6ee9be78f77204109a5 (MD5)
  • description.provenance : Made available in DSpace on 2013-11-20T18:40:38Z (GMT). No. of bitstreams: 1 HenryCalvinOscar1975.pdf: 679526 bytes, checksum: eb0250878b29f6ee9be78f77204109a5 (MD5) Previous issue date: 1973-08-09
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-11-20T18:40:38Z (GMT) No. of bitstreams: 1 HenryCalvinOscar1975.pdf: 679526 bytes, checksum: eb0250878b29f6ee9be78f77204109a5 (MD5)
  • description.provenance : Submitted by Georgeann Booth (gbscannerosu@gmail.com) on 2013-11-20T01:03:33Z No. of bitstreams: 1 HenryCalvinOscar1975.pdf: 679526 bytes, checksum: eb0250878b29f6ee9be78f77204109a5 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items