Ist alles, was man in einem Mikrocontroller programmieren kann auch theoretisch auch mit (beliebig großen) diskreten Schaltungen realisierbar? Sprich: Gibt es eigentlich so etwas wie Turing-Vollständigkeit bei "analogen" Schaltungen? Bzw. gibt es eine kleinste Menge Bauteilarten, aus denen alles beliebige baubar ist? Ich war nie gut in Rechnerarchitektur auf der Uni, aber ich habe das Gefühl, dass mein Prof. das irgendwie mit vollständiger Induktion beweisen hätte können. Der konnte alles ;) Das ist auch jetzt übrigens keine Hausarbeit oder so, ich bin von dem Fach auch schon 'ne Weile weg, ich hab mich das nur gerade gefragt, und wusste spontan keine Antwort..
@ Arne W. (Gast) >Ist alles, was man in einem Mikrocontroller programmieren kann auch >theoretisch auch mit (beliebig großen) diskreten Schaltungen >realisierbar? Ja. >Sprich: Gibt es eigentlich so etwas wie Turing-Vollständigkeit bei >"analogen" Schaltungen? Mikrocontroller sind digital, die logikkompatiblen Dikretschaltungen sind es auch. > Bzw. gibt es eine kleinste Menge Bauteilarten, >aus denen alles beliebige baubar ist? Tranistor.
> Bzw. gibt es eine kleinste Menge Bauteilarten, > aus denen alles beliebige baubar ist? Jede Logik-Schaltung kann aus NAND oder NOR Gattern aufgebaut werden. Demnach kannst du auch eine Menge an Bauteilen bestimmen, die du für ein NAND oder NOR Gatter brauchst. Also Transistor und ein paar passive Bauteile. Gruß, Edson
Klar, der Mikrocontroller besteht auch nur aus diskreten Bauelementen... Also alles was der Mikrocontroller in digitaler Hinsicht kann ist durch nand-Gatter realisierbar. Du kannst also mit diskreten Bauelementen (nand-Gattern) deinen Mikrocontroller nachbauen und dann kann er alles was er auch so kann.... ;-D AD-Wandlung, etc fällt in den Analogen-Bereich. Hier lässt sich keine kleinste Menge angeben (zumindest meiner Meinung nach).
Wobei ein NOR Gatter aus einem Transistor (z.B. NPN) und drei
Widerständen hergestellt werden kann.
VCC
|
|~|
|_| 1k
|
10k +-------o Out
In1 o--[====]---+ |
| |/
+--------| BC546
| |\>
In2 o--[====]---+ |
10k |
GND
Ein klares Jain! Eine Turing-Maschine hat ein unendlich langes Band. Sie hat somit unendlich viel Speicher. Der Grund warum man Mikrocontroller trotzdem noch, streng genommen falsch, als Turing-vollständig ansieht ist, dass sie "genügend" Speicher haben. Also streng genommen kann es keine realen Turing-Maschinen geben. Wenn Du "genügend Speicher" auf ein paar Bits reduzierst wird aber auch jeder endliche Automat zur Turing-Maschine. In Transistoren kannst Du diskret aber problemlos Computer bauen. Bis in die 1960ger Jahre waren fast alle Computer so aufgebaut. Hier mal ein Beispiel aus einem PDP-8, ein sehr populärer US-amerikanischer Computer: http://commons.wikimedia.org/wiki/File:Okona-GfhR-DEC-PDP-8-Logikgatter.jpg http://en.wikipedia.org/wiki/PDP-8
Christian Berger schrieb: > Ein klares Jain! Ein klares JA > Eine Turing-Maschine hat ein unendlich langes Band. Sie hat somit > unendlich viel Speicher. Der Grund warum man Mikrocontroller trotzdem > noch, streng genommen falsch, als Turing-vollständig ansieht ist, dass > sie "genügend" Speicher haben. Ja weil bei der Turingmaschine eben eine Speicherbegrenzung keine Rolle spielen soll, weil es eben nicht auf den Speicher, sondern auf die Grundsätzliche Berechenbarkeit eines Problems ankommt. > Also streng genommen kann es keine realen Turing-Maschinen geben. Wenn > Du "genügend Speicher" auf ein paar Bits reduzierst wird aber auch jeder > endliche Automat zur Turing-Maschine. Nicht nur streng genommen sondern ganz einfach. Es kann keine Turingmaschine geben. Das war aber auch nicht die Frage. Es geht um Turing-Vollständig und das bezieht sich allein auf die Berechenbarkeit und nicht auf den Speicher oder die Rechenzeit oder onst was. Also spielt es dafür keine Rolle ob nun eine Turingmaschine real existieren kann oder nicht. Und somit ist die Antwort auf die Ursprüngliche Frage ein klares JA und sonst gar nichts. Dies würde auch dann gelten wenn ein Controller überhaupt keinen Speicher hätte, weil es hier einzig auf die ALU ankommt, d.h. vorallem welche Kontrollstukturen existieren. Und als Kontrollstruktur reicht bereits ein WHILE oder sogar nur ein GOTO aus bzw. Befehle welche diese Nachbilden können. Das wird auch klar wenn man sich die Definition von Turing-Vollständigkeit ansieht. Dazu muss jedes math. Problem lösbar sein welches mit einem Algorithmus gelöst werden kann. Dabei spielen in der realen Welt natürlich IMMER Begrenzungen eine Rolle. Diese Begrenzungen haben aber keinen Einfluss auf die Tatsache ob eine logische Einheit Turing-Äquivalent ist oder nicht. Und btw: Ein DFA/NFA ist nicht Turing-Äquivalent. Eine Turingmaschine welche sich nur in eine Richtung bewegt UND nur lesen kann, entspricht einem NFA. gruß cyblord
Arne W. schrieb: > Ist alles, was man in einem Mikrocontroller programmieren kann auch > theoretisch auch mit (beliebig großen) diskreten Schaltungen > realisierbar? Ja. Du kannst ja jedes Programm auf einen endlichen Graphen abbilden. Endliche Graphen kannst Du dann zB als Statemachine aufbauen. > Sprich: Gibt es eigentlich so etwas wie Turing-Vollständigkeit bei > "analogen" Schaltungen? Eigentlich nicht. Analoge Systeme kannst Du ja nicht auf ein ENDLICHES Alphabet abbilden (zB liegt zwischen zwei unterschiedlichen (idealen) Spannungen immer eine Dritte, nämlich ihr Mittelwert). Damit ist der Begriff Turing-Vollständigkeit aber nicht mehr anwendbar. Mir ist zumindest kein Beweis der Turing-Vollständigkeit für |\Zeta|->\inf gekannt. > Bzw. gibt es eine kleinste Menge Bauteilarten, aus denen alles beliebige baubar > ist? Streng genommen auch nicht. Du kannst z.B. keinen Generator für "echte" Rechtecksignale bauen. Irgendeine Rise-/Falltime hat man immer. Ladungsträger brauchen halt ihre Zeit ;-) Da gibt es einfach nix um das zu realisieren. Da ist halt Physik die Basis und nicht Mathematik, wie bei Software. Grüße Andreas
Ist eigentlich bekannt, wie viele logische Verknüpfungen für eine touring-vollständige Maschine theoretisch nötig sind?
Zumindest gibts Leute die versuchen CPUs aus vielen standard Logikchips zu basteln: http://mycpu.thtec.org/www-mycpu-eu/clones.htm http://www.mycpu.eu/ http://mycpu.thtec.org/www-mycpu-eu/pictures/pic_mycpu21.jpg Jetzt stell Dir noch vor das die ganzen standard Logikchips da diskret aus einzelnen Transistoren aufgebaut wären ;-)
So hier noch die anderen Links... (Forum Spamschutz) Ach gerade mal geschaut, auf die Idee ist schon wer gekommen, zumindest Teilweise ein paar Chips sind noch dabei: http://www.6502.org/users/dieter/mt15/mt15_cpu_down2.jpg http://www.6502.org/users/dieter/mt15/mt15_sch.htm http://www.6502.org/users/dieter/mt15/mt15_carry.jpg http://www.6502.org/users/dieter/mt15/mt15_alu.jpg http://www.6502.org/users/dieter/mt15/mt15_pla_top.jpg ;-)
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.