AGI - ein Versuch das Thema 'Bewusstsein' zu lösen
01.06.2020 um 19:16Mal ein nettes Beispiel für einen deterministischen Algorithmus der nicht turing berechenbar ist.
Klassisch nimmt man da gerne das Halteproblem für Algorithmen, gibt aber unendlich viele unentscheidbare Probleme.
Thompsons Lampe ist ein Experiment bei der der Schalter einer Lampe immer nach dem verstreichen eines bestimmten Zeitintervalls ein bzw. ausgeschaltet wird.
Nach 1min wird die Lampe abgeschaltet.
Nach 1min + 1/2 min wieder angeschaltet.
Nach 1min + 1/2 min + 1/4 min wieder abgeschaltet
.
.
.
Die Reihe konvergiert gegen 2. Zwischen 1Min und 2 Minute wurde die Lampe unendlich oft ein und ausgeschaltet.
Leuchtet die Lampe nun oder nicht?
Das ist ein Beispiel für einen Supertask, da unendlich viele Rechenschritte zur Berechnung benötigt werden.
Physikalisch ist das nicht möglich, hier in diesem Universum, aber das spielt hier keine Rolle.
Sei n eine algorithmische Beschreibung für Thompson's Lampe, f eine Turingmaschine die Thompson's Algorithmus entscheiden soll.
f(n) = 1 genau dann wenn Thompson's Lampe 1 ausgibt.
f(n) = 0 genau dann wenn Thompson's Lampe 0 ausgibt.
f ist nicht turing berechenbar, da eine TM nur eine finite Anzahl von Rechenoperationen in endlicher Zeit durchführen kann.
Es gibt also Algorithmen / Funktionen, die nicht algorithmisch berechenbar sind.
Klassisch nimmt man da gerne das Halteproblem für Algorithmen, gibt aber unendlich viele unentscheidbare Probleme.
Thompsons Lampe ist ein Experiment bei der der Schalter einer Lampe immer nach dem verstreichen eines bestimmten Zeitintervalls ein bzw. ausgeschaltet wird.
Nach 1min wird die Lampe abgeschaltet.
Nach 1min + 1/2 min wieder angeschaltet.
Nach 1min + 1/2 min + 1/4 min wieder abgeschaltet
.
.
.
Die Reihe konvergiert gegen 2. Zwischen 1Min und 2 Minute wurde die Lampe unendlich oft ein und ausgeschaltet.
Leuchtet die Lampe nun oder nicht?
Das ist ein Beispiel für einen Supertask, da unendlich viele Rechenschritte zur Berechnung benötigt werden.
Physikalisch ist das nicht möglich, hier in diesem Universum, aber das spielt hier keine Rolle.
Sei n eine algorithmische Beschreibung für Thompson's Lampe, f eine Turingmaschine die Thompson's Algorithmus entscheiden soll.
f(n) = 1 genau dann wenn Thompson's Lampe 1 ausgibt.
f(n) = 0 genau dann wenn Thompson's Lampe 0 ausgibt.
f ist nicht turing berechenbar, da eine TM nur eine finite Anzahl von Rechenoperationen in endlicher Zeit durchführen kann.
Es gibt also Algorithmen / Funktionen, die nicht algorithmisch berechenbar sind.