Robotrontechnik-Forum

Registrieren || Einloggen || Hilfe/FAQ || Suche || Mitglieder || Home || Statistik || Kalender || Admins Willkommen Gast! RSS

Robotrontechnik-Forum » Technische Diskussionen » Gibt es hier jemand, der sich mit theoretischer Informatik beschäftigt? » Themenansicht

Autor Thread - Seiten: -1-
000
10.10.2014, 13:46 Uhr
Rüdiger
Administrator


Ich würde gern mal mit jemand zum Thema Turing-Vollständigkeit diskutieren.

Ich halte es für denkbar, dass bestimmte Geräte aus der EDV-Frühzeit dem Zuse Z3 seinen Rang als ersten Computer streitig machen könnten.
--
Kernel panic: Out of swap space.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
001
10.10.2014, 14:37 Uhr
Hobi



Welche denn?
--
-------------------------------------------
Corontäne
-------------------------------------------
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
002
10.10.2014, 17:56 Uhr
bernard



http://www.turing.org.uk/turing/scrapbook/computer.html

Für Turing der Krieg hat ein Vorteil gegeben. Sein Entwurf war mit Geld den Kriegskonto untergestutzt

Zuse hat keinen Geld von Regierung bekommen

Turing glaubt ein Maschine konnte viele unterschiedlichen Arbeit unternehmen.

Zuse glaubt mehrer unterschiedlichen Machinen waren notwendig fur unterschiedlichen Typen Arbeit
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
003
11.10.2014, 17:12 Uhr
waldheinz



Ein Freund von mir hat ganz gut was drauf in theoretischer Informatik, mit Doktortitel und allem. Der könnte sich zu dem Thema bei einem Bier vielleicht eine Meinung bilden. Kannst Du irgendwelche Unterlagen zu den entsprechenden Geräten, die ich Ihm mal zeigen könnte?
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
004
12.10.2014, 13:48 Uhr
Thomas



Rüdiger, wie kommst Du gerade jetzt auf Turing? Hängt das mit dem neuen Film The Imitation Game zusammen?
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
005
12.10.2014, 16:01 Uhr
Rüdiger
Administrator



Zitat:
Thomas schrieb
Hängt das mit dem neuen Film The Imitation Game zusammen?



Nein.
--
Kernel panic: Out of swap space.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
006
13.10.2014, 12:49 Uhr
Rüdiger
Administrator



Zitat:
Hobi schrieb
Welche denn?



z.B Continental Klasse 800.
--
Kernel panic: Out of swap space.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
007
13.10.2014, 14:02 Uhr
Hobi



Gibt es dazu einen Wiki Link? So richtig kann ich nichts finden.


Zitat:
Die erste Maschine, von der die Turing-Vollständigkeit sicher bekannt ist, ist die programmgesteuerte Z3 von Konrad Zuse



Der Wert der Turing-Vollständigkeit ist aber nur akademischer Natur, da die Maschine dazu eigentlich nicht fähig ist. Erst durch etwas Trickersei kann man z.B. einen bedingten Sprung nachbilden. So ist die Z3 per Definition ein Universalrechner, wurde aber als solche nie benutzt, noch wusste der Konstrukteur davon.

Unabhängig davon glaube ich immernoch nicht, dass es vor der Z3 Universalrechner gab zumal die Welt damals sehr übersichtlich war. Mehr als 10 Computer waren bis in die 50er nie geplant (Zitat IBM)
--
-------------------------------------------
Corontäne
-------------------------------------------

Dieser Beitrag wurde am 13.10.2014 um 14:25 Uhr von Hobi editiert.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
008
13.10.2014, 14:56 Uhr
Rüdiger
Administrator



Zitat:
Hobi schrieb
Gibt es dazu einen Wiki Link?



Nein.


Zitat:
Erst durch etwas Trickersei kann man z.B. einen bedingten Sprung nachbilden. So ist die Z3 per Definition ein Universalrechner



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.




Zitat:
Unabhängig davon glaube ich immernoch nicht, dass es vor der Z3 Universalrechner gab



Das hängt nicht von Deinen Glauben ab: Hier geht's um historische Fakten.
Kann durchaus sein, dass meine Rechner am Turingtest scheitern. Aber das will ich eben prüfen...
--
Kernel panic: Out of swap space.

Dieser Beitrag wurde am 13.10.2014 um 14:57 Uhr von Rüdiger editiert.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
009
14.10.2014, 00:21 Uhr
Hobi



Vielleicht haben wir uns ja missverstanden, hier geht es nicht um glauben. Das die Z3 ein Universalrechner ist, ist ein Fakt. Es ist dein Beispiel an welches ich nicht glaube, solange ich kleine Fakten habe.

Gibt es eventuell Hintergrundinformationen von dir betreffs Continental Klasse 800 ?
--
-------------------------------------------
Corontäne
-------------------------------------------
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
010
14.10.2014, 00:57 Uhr
rm2
Default Group and Edit
Avatar von rm2

Hallo an alle,

in der englischsprachigen Welt wird immer Alan Turing derjenige sein, in der deutschsprachigen Welt immer Konrad Zuse. Deshalb sind viele Publikationen voreingenommen. Das ist leider so, auch auf anderen Gebieten.

Eine wirklich unabhängige Analyse muss von Wissenschaftlern erst noch erstellt werden (1. Indikator ist die Finanzierung).

Inwieweit bisherige Darstellungen überhaupt Kenntnis von der Leistungsfähigkeit mechanisch/elektrischer "Automaten" haben, bleibt vollkommen im Dunkeln. In allen diesen Publikationen fehlt die Referenz der analysierten Systeme.

Ob die "Automaten" in Bletchley Park auch noch etwas anderes konnten wurde meines Wissens nie dokumentiert.



mfg ralph
--
.
http://www.ycdt.net/mc80.3x . http://www.ycdtot.com/p8000
http://www.k1520.com/robotron http://www.audatec.net/audatec
http://www.ycdt.de/kkw-stendal
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
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.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
012
16.10.2014, 11:15 Uhr
Hobi



Sehr schön formuliert. Und auch noch recht verständlich. ++
--
-------------------------------------------
Corontäne
-------------------------------------------
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
013
16.10.2014, 15:13 Uhr
Rüdiger
Administrator



Zitat:
Hobi schrieb
Gibt es eventuell Hintergrundinformationen von dir betreffs Continental Klasse 800 ?



Ich beabsichtige, Ende des Jahres ein Kapitel zu der Maschine in die Website einzufügen.
Funktionell hat die Ähnlichkeiten mit Optimatic und Ascota Klasse 170.
--
Kernel panic: Out of swap space.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
014
17.10.2014, 13:44 Uhr
waldheinz




Zitat:
Hobi schrieb
Sehr schön formuliert. Und auch noch recht verständlich. ++



Danke. :-)

Ich habe auch zwischenzeitlich beim Profi nachgefragt und darf vermelden, dass ich keinen Quatsch erzählt habe. Ergänzend sei aber noch auf die WHILE- [1] und die GOTO - Berechenbarkeit [2] hingewiesen, welche beide ebenfalls Turing - vollständig sind. Vielleicht macht das den Nachweis einfacher.

Für das Gegenteil, also den Nachweis der nicht - Turing - Vollständigkeit, gibt es jedoch kein einfaches Rezept. Man sieht ja auch recht schön an der Z3, dass sowas gefährlich wäre. Von der dachte man ja auch, dass sie nicht T-V wäre, und dann kommt jemand daher und zeigt dass es eben doch geht.

[1]: http://de.wikipedia.org/wiki/WHILE-Programm
[2]: http://de.wikipedia.org/wiki/GOTO-Programm
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
015
17.10.2014, 14:28 Uhr
Rüdiger
Administrator


Mit der Computerdefinition ist das eine vertrackte Sache:
Die deutsche Wikipedia hält die Turing-Vollständigkeit für essentiell.
Das würde aber bedeuten, dass der Atanasoff-Berry-Computer kein Computer wäre. Analogcomputer würden da wohl auch herausfallen.

Die englische Wikipedia (und auch das Oxford English Dictionary) legen auf die Turing-Vollständigkeit keinen Wert, setzen nicht einmal die Ausführbarkeit arithmetischer Operationen voraus. Damit wären Hollerith-Lochkartensortierer oder programmierbare Zähler auch bereits Computer...



Zitat:
Ergänzend sei aber noch auf die WHILE- [1] und die GOTO - Berechenbarkeit [2] hingewiesen,



Beide Operationen kann ich mit der 1937er Maschine ausführen:

GOTO:
Es gibt ein vorwärts-gerichtetes GOTO und ein rückwärts-gerichtetes GOTO.
Allerdings sind bei Verschachtelung mehrerer GOTOs Grenzen gesetzt.

Das Programm besitzt außerdem am Programmende einen impliziten Sprung zum Programmanfang (=Hauptprogrammschleife), womit also jedes Programm endlos laufen kann.

While:
Es gibt eine Vergleichsfunktion, ob eine Zahl größer oder kleiner Null ist. Abhängig davon kann ein Sprung per vorwärts-gerichtetem GOTO ausgelöst werden.
--
Kernel panic: Out of swap space.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
016
18.10.2014, 17:20 Uhr
bernard



Ich bin der Meinung das ein calculator der algorythm kann nicht anderung. Der Formula ist fest.

Ein computor der Algorythm kann anderung abhangig von Data
Der Fomula ist nicht fest
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
017
20.10.2014, 21:53 Uhr
waldheinz



@Rüdiger Was die Flusskontrolle angeht ist das ja schon mal nicht schlecht, könntest Du vielleicht noch ein paar technische Daten zu der / den Gerät(en) verraten? Insbesondere, wie der verfügbare Speicher organisiert war. Ich nehme an, es gab ein paar Register. Wie viele und wie breit waren die? Ausgabe auf Papier war bei einer Buchungsmaschine sicherlich vorhanden, gab es evtl. auch Lochstreifen?

Eine Übersicht über den Befehlssatz wäre sehr Hilfreich. Wie war der Programmspeicher implementiert?

Ich werde evtl. diese Woche nochmal eine Sitzung mit meinem Bekannten machen, dann hätten wir wieder was zum Diskutieren. :-)

Dieser Beitrag wurde am 20.10.2014 um 22:42 Uhr von waldheinz editiert.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
018
21.10.2014, 11:54 Uhr
Rüdiger
Administrator



Zitat:
waldheinz schrieb
@Rüdiger Was die Flusskontrolle angeht ist das ja schon mal nicht schlecht, könntest Du vielleicht noch ein paar technische Daten zu der / den Gerät(en) verraten?



Ich schreibe Dir eine längere Email.


Zitat:
Ich nehme an, es gab ein paar Register.
Wie viele und wie breit waren die?



Ja, 10.
Je 12 Dezimalstellen.



Zitat:
Ausgabe auf Papier war bei einer Buchungsmaschine sicherlich vorhanden,



Ja.


Zitat:
gab es evtl. auch Lochstreifen?



Nicht bei dieser.
--
Kernel panic: Out of swap space.
Seitenanfang Seitenende
Profil || Private Nachricht || Suche Zitatantwort || Editieren || Löschen
Seiten: -1-     [ Technische Diskussionen ]  



Robotrontechnik-Forum

powered by ThWboard 3 Beta 2.84-php5
© by Paul Baecher & Felix Gonschorek