Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/6107Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.creator | Cooke, John | - |
| dc.creator | Minsky, Marvin | - |
| dc.date | 2004-10-04T14:39:33Z | - |
| dc.date | 2004-10-04T14:39:33Z | - |
| dc.date | 1963-04-01 | - |
| dc.date.accessioned | 2013-10-09T02:43:01Z | - |
| dc.date.available | 2013-10-09T02:43:01Z | - |
| dc.date.issued | 2013-10-09 | - |
| dc.identifier | AIM-052 | - |
| dc.identifier | http://hdl.handle.net/1721.1/6107 | - |
| dc.identifier.uri | http://koha.mediu.edu.my:8181/xmlui/handle/1721 | - |
| dc.description | In the following sections we show, by a simple direct construction, that computations done by Turing machines can be duplicated by a very simple symbol manipulation process. The process is described by a simple form of Post Canonical system with some very strong restrictions. First, the system is monogenic; each formula (string of symbols) of the system can be affected by one and only one production (rule of inference) to yield a unique result. Accordingly, if we begin with a single axiom (initial string) the system generates a simply ordered sequence of formulas, and this operation of a monogenic system brings to mind the idea of a machine. The Post canonical system is further restricted to be of the "Tag" variety, described briefly below. It was shown in [1] that Tag systems are equivalent to Turing machines. The proof in [1] is very complicated and uses lemmas concerned with a variety of two-tape non-writing Turing machines. Our proof here avoids these otherwise interesting machines and strengthens the main result, obtaining the theorem with a best possible "deletion number" P ?? Also, the representation of the Turing machine in the present system has a lower degree of exponentiation, which may be of significance in applications. These systems seem to be of value in establishing unsolvability of combinatorial problems. | - |
| dc.format | 1314819 bytes | - |
| dc.format | 1026648 bytes | - |
| dc.format | application/postscript | - |
| dc.format | application/pdf | - |
| dc.language | en_US | - |
| dc.relation | AIM-052 | - |
| dc.title | Universality of TAG Systems with P-2 | - |
| Appears in Collections: | MIT Items | |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.