The complex behavior of simple machines
dc.contributor.author | Machlin, Rona | en_US |
dc.contributor.author | Stout, Quentin F. | en_US |
dc.date.accessioned | 2006-04-10T13:42:20Z | |
dc.date.available | 2006-04-10T13:42:20Z | |
dc.date.issued | 1990-06 | en_US |
dc.identifier.citation | Machlin, Rona, Stout, Quentin F. (1990/06)."The complex behavior of simple machines." Physica D: Nonlinear Phenomena 42(1-3): 85-98. <http://hdl.handle.net/2027.42/28528> | en_US |
dc.identifier.uri | http://www.sciencedirect.com/science/article/B6TVK-46G4VN3-9/2/d0d21c4c5d425c4ca6e7378f34c730b6 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/28528 | |
dc.description.abstract | This paper interprets work on understanding the actions of Turing machines operating on an initially blank tape. While this is impossible for arbitrary machines, complete characterizations of behavior are possible if the number of states is sufficiently constrained. The approach combines normalization to drastically reduce the number of machines considered, human-generated classification schemes, and computer-generated proofs of behavior. This approach can be applied to other computational systems, giving complete characterizations in sufficiently small domains. This is of interest in the area of emergent systems since the properties of such systems are often difficult to determine. By using computers to eliminate multitudes of machines with well understood behavior, some unanticipated exotic machines with complex behavior were discovered. These exotic machines show that it is quite difficult to estimate the number of states needed to produce a given behavior, and hence subjective estimates of complexity may be poor approximations of the true complexity. | en_US |
dc.format.extent | 1039873 bytes | |
dc.format.extent | 3118 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Elsevier | en_US |
dc.title | The complex behavior of simple machines | en_US |
dc.type | Article | en_US |
dc.rights.robots | IndexNoFollow | en_US |
dc.subject.hlbsecondlevel | Physics | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109-2122, USA | en_US |
dc.contributor.affiliationother | Relational Technology, Park 80 West Plaza 1, Saddle Brook, NJ 07662, USA | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/28528/1/0000325.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1016/0167-2789(90)90068-Z | en_US |
dc.identifier.source | Physica D: Nonlinear Phenomena | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.