011
14.10.2014, 11:04 Uhr
waldheinz
|
| Zitat: | | Erst durch etwas Trickersei kann man z.B. einen bedingten Sprung nachbilden. So ist die Z3 per Definition ein Universalrechner |
Das ist so nicht ganz richtig. Die Z3 wird als Universalrechner betrachtet, weil sie durch den "getricksten" bedingten Sprung befähigt wird, eine universelle Turing - Maschine zu emulieren. Da die Turing - Vollstädigkeit eben über die Berechenbarkeit auf einer UTM definiert ist folgt natürlich, dass die Z3 auch Turing - vollständig ist. Die Turing - Vollständigkeit der Z3 folgt also nicht einfach aus dem Vorhandensein eines bedingten Sprungs, sondern aus der Tatsache, dass man eine UTM auf die Z3 "reduzieren" kann. Der bedingte Sprung ist da "nur" ein Element, was benötigt wird.
| Zitat: | Rüdiger schrieb
Bedingte Sprünge kann mein angesprochener Rechner. Ebenso mathematische Berechnungen, Programmschleifen, Daten speichern und wieder lesen.
Und er ist programmierbar. Ich vermag aber nicht festzustellen, ob das bereits alle Kriterien einer Turingmaschine erfüllt, weil mir der Hintergrund der Definition der Turing-Vollständigkeit fehlt. Also eine Kriterienliste, die ich auf Erfolg oder Misserfolg überprüfen/abarbeiten kann.
|
Um die Turing - Vollständigkeit nachzuweisen, wäre es hinreichend eine beliebige UTM auf dem entsprechenden Gerät zu emulieren. Es gibt eine ganze Reihe UTMs, ein hilfreicher Suchbegriff ist "small universal turing machine". Welche von denen Du wählst ist reine Geschmackssache, sie sind ja alle universell (und damit aufeinander reduzierbar). Es gibt welche die benötigen gerade mal vier Zustände und sechs Symbole, aber im Endeffekt wird man halt etwas wählen, was gut auf die Zielarchitektur passt. Es ist vielleicht hilfreich, erst mal eine UTM in einer beliebigen Hochsprache zu implementieren, um ein Gefühl für die Problematik zu bekommen.
Bevor man allzu viel Zeit in die Sache investiert, wäre es aber vielleicht clever zu schauen, ob man nicht das Gegenteil beweisen kann -- vielleicht geht das ja schneller. Ich werde mal nachfragen, wie so ein Beweis aussehen könnte, da fehlt mir gerade die Vorstellungskraft. Also abgesehen davon, dass das Fehlen eines bedingten Sprungs ein sicheres K.O. - Kriterium ist.
| Zitat: |
Kann durchaus sein, dass meine Rechner am Turingtest scheitern. Aber das will ich eben prüfen... |
Der Turing-Test ist aber schon was anderes. :-)
Dieser Beitrag wurde am 14.10.2014 um 11:05 Uhr von waldheinz editiert. |
