Original at: http://cis.csuohio.edu/~somos/bb.html
Turingmaschine der Fleißigen Biber
Die Geschichte beginnt ungefähr im Jahre 1960. Tibor Rado ein Professor an Ohio State University denkt an einfache unberechenbare Funktion – entscheidbares Halteproblem für Turingmaschine. Wenn man dieser Turingmaschine eine fixierte finite Zahl von Symbolen und Eigenschaften eingibt, hält eventual das Programm, das mit leerem Band getrieben ist. Unter diesen Programmen wird eine maximale Zahl von nicht-leeren Symbolen links auf dem Band, wenn sie halten, gefunden. Alternativ wird Maximale Anzahl von Zeitschritten vor Halten gefunden. Diese Funktion ist gut definiert, aber plötzlich wird sie nicht berechenbar sogar für eine kleine Anzahl von Zahlen und Symbolen.
In 1962 hat Tibor Rado einen Artikel darüber veröffentlicht, aber er schrieb nur von einem theoretischen Ergebnis. Mit seinem Studenten Shen Lin, haben sie eigentlich zwei Symbole angefasst, drei-Eigenschaften-Problem. Die Forschung ergab sich in eine Dissertation für Lin in 1963 und einen Artikel in JACM iin 1965. Nach der anfänglichen Artikelaufregung erschienen andere bemerkenswerte Ergebnisse. Der populärste ist vielleicht August 1984 Scientific American Computer Recreations column von Dewdney. Es gibt ein PostScript handout von Jeffrey Shallit über das Problem.
Biber Turingmaschine Artikel
- An unberechenbare Funktionen, Tibor Rado, The Bell System Technical Journal, vol. XLI, no. 3, May 1962, pp. 877-884.
Es ist Originalartikel, das das Problem beschreibt. Es ist ein theoretischer Artikel, und er gibt nur ein Beispiel von semi-entscheidbarem Problem.Shen Lin und Tibor Rado. Computer studies of Turing machine problems. Journal of the ACM, 12(2):196-212, April 1965.
Dieser Artikel beschreibt eigentlich das Prozess, das zur Lösung von Drei-Eigenschaften-Problem geführt hat. Viele Details über Maschine. Hier gibt es eine Liste von 40 Maschinen, die eine menschliche Analyse brauchten. Der Artikel gründet sich auf Shen Lin's Thesis Ergebnissen.Bestimmung von Bedeutung Rado's nicht-berechenbarer Sigma(k) Funktion für Vier-Zustände Turing Machinen von Allan H. Brady, Mathematics of Computation, vol. 40, no. 162, Apr 1983, pp. 647-665.
Dieser Artikel enthält eine Beschreibung von Prozess, der zur Lösung Vier-Eigenschaften-Problems geführt hat. Er bezieht sich auf seiner Thesis in 1964. Der Artikel enthält viele Beispiele von einem guten Benehmen, das Maschinen uns zeigen können.KomplexBenehmen von einfachen Maschinen, von Rona Machlin und Quentin F. Stout, Physica vol. 42D, 1990, pp. 85-98.
- Dieser Artikel präsentiert eine unabhängige Lösung von vier-Eigenschaften-Problem. Er gibt eine gute Beschreibung von Baum-normal Methode. Er enthält eine reiche Beschreibung von Maschinen inklusive einige fünf-Eigenschaften-Exemplare von Juergen Buntrock und Heiner Marxen. Einen Auszug gibt es im Internet. Dieser Jahrgang von Physica D erschien in Form eines Buches "Emergent Computation" unter Redaktion von Stephanie Forrest veröffentlicht von MIT Press und inspiriert von 1989 Los Alamos Conference für auftauchende Rechnungen.
- Computer Recreations, von A.K. Dewdney, Scientific American, Apr 1985, p. 30.
- Dieser Artikel gibt Uhing fünf-Eigenschaften-Bewerber und erwähnt Suchprozess unterstützenden Mikroprozessor. Serin‘s Interesse wurde durch Artikel von Dewdney (August 1984) erweckt. Die aktuelle Aufnahme für sechs Eigenschaften ist 95,524,079 Punkte in 8,690,333,381,690,952 Schritte von Heiner Marxen nach Maßgabe von paper in PostScript von Jeffrey Shallit.
Turing Maschine Information
Für eine schnelle Vorstellung von Turing Maschinen besuchen Sie Turing's Welt Seite in Stanford. Heiner Marxen hat eine gute web Seiteüber Fleißiger Biber und seinen eigenen Bewerbern.