Schreibschlitten von Hinten

Ja wie herrlich! Ganz allerliebst (und grau ;-)! So ganz hab ich die Funktionsweise aber noch nicht verstanden. RoboPro steuert das Ganze, liest Bits und verarbeitet die nach festen Regeln, und schreibt in den Bitspeicher zurück? Wie funktioniert dann die Addition, und was genau wird da addiert? Gruß, Stefan

Hallo Stefan,

Ja – ich hatte kein anderes Foto von hinten … Alles in grau – damit baue ich halt und die Eingaben werden halt addiert - also genauer:

Wenn man sich noch nicht mit Turingmaschinen beschäftigt hat wird’s für mich schwierig das zu erklären – ich versuch es.

Zur fundamentalen Bedeutung siehe http://de.wikipedia.org/wiki/Turingmaschine

An Wikipedia angelehnt: Formal kann eine deterministische Turingmaschine als 7-Tupel M= (Q, E,T, d, q0, 0, qf) dargestellt werden.

Hier im Modell: Q= Zustandsmenge je nach Aufgabenstellung (siehe unten Addition q1 bis q5) . E =Eingabe = {1} = BS nach vorn. T = Bandalphabet {BS vorn , BS hinten} {0,1} d – Wird über eine Überführungsfunktion definiert. Hier als Quintupel definiert siehe unten. q1 = Anfangszustand 0 = BS hinten qf = ist der akzeptierende Zustand

Bsp. Addition:

Werden Zahlen in der unären Darstellungsform notiert, so gilt:

Eine beliebige Zahl a ( a ) wird durch a aufeinanderfolgende „1“-en dargestellt, 11 entspricht der „2“ im Dezimalsystem 111 entspricht der „3“ (3 Einsen).

Ziel Addition: Zwei durch ein „0“ getrennte beliebige unäre Zahlen werden so addiert dass das Ergebnis am Ende als unäre Zahl auf dem Turingband steht.

Also hier 11111

2 + 3 Anfang Turingband: 00001101110000

Ergebnis: 0000111110000

Ein Turingprogramm einer einbändigen Turingmaschine besteht aus einer Menge Q – siehe Oben und Quintupeln d der Form (q, s, s’, d, q’)

• q ist der aktuelle Zustand (im Programm von RoboPro gemerkt siehe unten bsp. Addition)
• s das vom Lesekopf gelesene Zeichen ( siehe Leseeinheit)
• s’ das an die Stelle von s zu schreibende Zeichen ( siehe Schreibmechanik)
• d die Bewegungsrichtung des Lese-/Schreibkopfes, in die das Band nach dem Berechnungsschritt zu bewegen ist {L,R,H} {rechts, links, halt}
• q’ der auf den Berechnungsschritt folgende neue einzunehmende Zustand

( in RoboPro als Tabelle umgesetzt): Die Quintupel der Addition: (1, 1, 1, R, 1) (1, 0,1,R, 2) (2, 1, 1, R, 2) (2, 0, 0, L ,3 ) (3, 1 , 0 , L, 4) (3, 0, 0, S, 3) (4, 1,1,L,4) (4, 0,0,R,5) (5, 1,1,H,5) (5,0,0,H,5)

Bei H = halt ist Schuss.

Die Turingmaschine wurde 1936 vorgestellt. Der Z3 von Konrad Zuse war 1941 der erste universell programmierbare (turingmächtige) Rechner.

Wer mehr über Komplexitätstheorie und die Hintergründe wissen will und warum solche Maschinen-Modelle existieren kann hier weiterlesen: http://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie#Die_erweiterte_Church-Turing-These

Gruß Thorsten

Ergänzung / Korrektur BS vorn = 1 und Zustand q0 = q1

Hallo Thorsten, sensationell. Eine Turingmaschine! Programmieren ohne Controller! Bitte, bitte einen Beitrag für die ft:pedia daraus machen… Gruß, Dirk

Hallo Dirk,

Turing (TM) ist wirklich der aktuellste Ansatz um anschaulich und effizient neueste Problemstellungen zu lösen und wird bald in den Verkauf kommen. Somit wäre ein Beitrag in der ft:pedia der Durchbruch zur Serienproduktion.

Nur an dem grauen Retro-Style muss noch gearbeitet werden – die Rastadapter werden noch durch alte Seilrollen ersetzt.

Manchmal verschweigen aber die Marketingabteilung das allein eine Fakultätsfunktion schon fast 80 Zustände verschlingt und 3! braucht 210 Rechenschritte. 4! 1908 Schritte - 5! ???

Aber da kommt dann das Argument des Verkaufleiters das bis auf polynomielle Faktoren die Turingmaschine zu aktuellen Rechnern z.B. dem chinesische Tianhe-2 mit 33,86 PFlops gleich mächtig ist.

Also bei meinem Prototyp liegen die OP’s / s bei 0,5 Hz. Und die auf die Wort/Bitbreite kommt es ja auch nicht an. Siehe auch Speedup-Theorem: http://de.wikipedia.org/wiki/Speedup-Theorem

Von der O-Notation her bin ich mit der Maschine auf dem Neusten stand der Technik. Das hört sich gut an.

Leider verschweigt das Management gerne das zur Steuerung selbst ein Controller für die Überführungsfunktion benutzt wird.

Aber das muss nicht sein!

Die Übergangsfunktion kann man auf Transitionsgraphen abbilden.

Über ein Schaltwerke für endliche Automaten kann man mit z.B. einigen ft Stufenschalter und deren Verkabelung + Taktgeber die Programmierung vornehmen. Da muss man noch die Fotowiderstände durch Schalter ersetzen. Schaltwerke für endliche Automaten: http://www.emu-online.de/imd3kap6.pdf

Oder gleich über Pneumatik und Schlauchverbindungen programmieren. Das hat schon jemand umgesetzt: http://texttheater.net/mechanische-turingmaschine Da kann man dann auch mit Luftschranken (s. Festo Pneumatik) arbeiten.

Die Stöpsel-Programmierung ist halt recht aufwändig, ist aber ein ganz neues UI–Erlebnis. Das könnte man auch gut in Volkshochschulkursen anbieten.

Also zur Stöpsel-Programmierung kann ich gerne mal einen ft:pedia Beitrag schreiben, aber die TM hab ich nur hochgeladen weil noch keine im Bilderpool war und sie gleich wieder abgebaut wurde.

Gruß Thorsten

Denkst Du noch an den oder die ft:pedia-Beiträge, Thorsten? :-)

Lechzender Gruß, Stefan