Re: Computer sind nicht nur Turingmaschinen

Wieder mal ein Text, der viel zu lang für das Heise-Forum wurde.

Text

Mal kurz eine Einführung:

Wir streiten hier gerade darüber, ob NP=P oder NP!=P.

Ich bin der Meinung, NP!=P, Du bist der Meinung, NP=P. Da ich glaube aber wir beide nicht intelligent genug sind, dieses Problem, an dem sich Mathematiker seit Jahrzehnten die Zähne ausbeißen, entscheiden können, glaube ich, dass wir letztendlich nicht zu einer Entscheidung kommen werden. OK?

Hybris schrieb am 26. Oktober 2005 10:04
> > Die Antwort ist ja so einfach:Es entscheidet sich nicht! Die
> > Reaktio bestimmt schlicht die Aktio die stattgefunden haben muss.
> > Und genau hier können Quantensysteme etwas leisten, das
> > Turingmaschinen selbst mit unendlich viel Zeit nicht leisten können.
>
> Und das hat nichts mehr mit Computern (endlichen deterministischen
> Maschinen) zu tun, womit wir wieder am Anfang wären.

Nein, Du verwechselst hier die Computer mit den Automaten.

Vor den Digitalcomputern gab es die Analogcomputer. Jetzt sag mir bitte nicht, dass Analogcomputer keine Computer sind. Analogcomputer sind zwar deterministisch, aber nicht endlich, da sie mit transzedenten Zahlen operieren können.

Ein Computer ist ein "Berechner". Ein Computer macht also in meinen Augen genau das, was die Wikipedia beschreibt:

Er berechnet aus Eingangsdaten mit einem Algorithmus irgendwelche Ausgangsdaten. Der Witz ist eben, dass der Algorithmus nichtdeterministisch sein kann. Jetzt erkläre mir bitte, wie Du einen nichtdeterministischen Algorithmus auf einer deterministischen Maschine implementieren willst!

Auf Quantencomputern kann man aber eine bestimmte Klasse von nichtdeterministischen Algorithmen implementieren. (Eine Klasse, das heißt nicht, dass alle nichtdeterministischen Algorithmen gehen!)

Sag nicht, dass das nicht sein kann, dann hast Du soeben die gesamte Kyptologie in die Tonne getreten. Ein kryptologischer Zufallsgenerator der keinen Pseudo-Zufall erzeugt, ist immer ein Nichtdeterminismus. Mit einem abgeschlossenen System a la Turingmaschine kannst Du keinen echten Zufallsgenerator betreiben, außer Du nimmst irgendwelche "externen" Hilfsmittel dazu (Tastatur, Uhrzeitchip zur Timingmessung, Temperaturfühler etc.).

Ein Quantencomputer kann das aber direkt implementieren, da sich Quanten nichtdeterministisch verhalten. Ein echter Zufallsgenerator ist also Teil eines Quantencomputers. Es ist aber schlimmer, denn dank Vielweltenansatz liefert dieser Zufallsgenerator alle Werte, inklusiver transzedenter Zahlen, also nicht nur Q wie in "endlichen deterministischen Automaten", sondern R, das eine wesentlich größere Mächigkeit hat.

Das wird oft verwechselt, da beide Mengen "dicht" liegen. Der Mensch kann sich den Unterschied zwischen R und Q eben nicht so richtig vorstellen. Quantencomputer verhalten sich wie R, während Turingmaschinen sich wie Q verhalten. (Deshalb kannst Du Gödel auf Quantensysteme nicht mehr anwenden.)

> > Was ich hier schreibe kann man hingegen fast alles in der Wikipedia
> > finden.
>
> Selbst das Wiki sagt:
>
> "Ein Quantencomputer kann prinzipiell genau dieselben Probleme
> berechnen wie ein klassischer Computer, da ein klassischer Computer
> einen Quantencomputer simulieren kann und umgekehrt."

Diese Aussage muss falsch sein. Ein Digitalcomputer kann schon einen Analogcomputer nicht mehr vollständig simulieren. Analogcomputer und Digitalcomputer können zwar prinzipiell dieselben Probleme berechnen, aber daraus kann man keine Emulierbarkeit/Simulierbarkeit folgern.

Dass ein Analogrechner nicht einmal simuliert werden kann lernst Du in der Numerik. Ich meine hier die die instablen numerischen Rechenverfahren. In einem Analogrechner kannst Du diese verwenden umein ordentliches Ergebnis zu bekommen, in einer Turingmaschine bekommst Du ggf. nur "liegt bei 0 mit einem Fehler von Unendlich". Tolle Aussage. (Hier ist entscheidend: Ich lasse den Analogcomputer von einer Turingmaschine emulieren. Natürlich kannst Du das Problem so umschreiben, dass es auf der Turingmaschine ebenso ein korrektes Ergebnis liefert. Das wäre aber keine Simulation, sondern eine Emulation! Wir sprechen hier von Simulationen, d. h. Du nimmst das konkrete Teil und simulierst es, Du veränderst diese Simulation nicht so, dass diese berechenbar wird, weil ein Schritt vielleicht nicht mit hinreichender Genauigkeit simuliert werden kann!)

Ein Quantencomputer kann auch mit transzedenten Zahlen operieren. Damit meine ich nicht nur, logisch umgehen, sondern schlichtweg PI berechnen. Bis auf die letzte Stelle, die es bei PI nicht gibt. Und das in endlicher (sogar konstanter) Zeit (das muss so sein, sonst gäbe es in der Natur keine Kreise).

Eine Turingmaschine (die übrigens ein unendlicher deterministierscher Automat ist und somit nach Deiner Aussage kein Computer) kann das nicht.

Somit ist eine Simulation einer Berechnung die im Quantensystem in konstanter Zeit abläuft nur mit unendlicher Zeit simulierbar.

Wie ich Feynman verstanden habe, meinte er das genau so. Nämlich dass die Quantensysteme in der Klasse der Algorithmen, die eine Turingmaschine berechnen kann, eben nur schneller sind. Nicht umgekehrt. Für den umgekehrten Fall habe ich keine Aussage im Web gefunden! Hast Du einen Pointer?

> Quelle: de.wikipedia.org/wiki/Quantencomputer

Ich bezweifle dass einer der führenden Quantenexperten diesen Artikel verfasst hat ;)

(Ich bin kein solcher, aber ich versuche von ihnen zu lernen, auch wenn das nur ein Hobby ist.)

> > Die Wikipedia definiert den Computer somit auch nicht als
> > Turingmaschine, sondern als System, das einen Algorithmus abarbeitet.
>
> Diese Definition wäre falsch, ganz gleich durch wen geäußert.

Hast Du beweise? Komisch ist nämlich, dass die ersten Computer genau das nicht getan haben was Du von ihnen behauptest.

In der Wikipedia stehen nicht nur wahre Dinge, das ist richtig. Ich nehme die Wikipedia deshalb nicht zur DEFINITION her, sondern um zu erfahren, ob ich mit meiner Meinung im Mainstream bin.

Wenn Du der Meinung bist, der Artikel um Computer ist falsch, dann editiere ihn. Ich habe festgestellt, dass das gar nicht so einfach ist, weil ich ein wichtiges Kriterium in der Wikipedia nicht erfüllen kann: Ich kann nicht objektiv urteilen, da ich subjektiv unterwegs bin.

[..]
> > Ich gehe davon aus (beweisen kann ich es nicht, aber deshalb nehme
> > ich an, Dein Feynman-Zitat ist falsch) dass man eine Klasse
> > Algorithmen in Quantenrechnern implementieren kann, für die eine
> > Turingmaschine unendlich viel Rechenzeit benötigt, und zwar
> > prinzipiell, mit dem besten Algorithmus.
>
> Nein, die Turingmaschine benötigt in jedem Fall endlich viel Zeit
> auch wenn sie über das Ende des Universums hinaus rechnen muss.

Das geht aber nur mit einer unendlich schnellen Turingmaschine, die also pro Sekunde unendlich viele Rechenoperationen durchführen kann.

Und erkläre mir bitte, wie die Turingmaschine sich anders verhalten kann, abhängig ob Du, Ich oder niemand sie ansieht? Der Witz dabei ist ja, der Quantenrechner kann das sogar jetzt entscheiden, wenn dieses Vorkommnis erst in der Zukunft passiert. In Quantensystemen gehen sehr seltsame Dinge vor.

Nochmals, nur damit Du es verstehst: Die Entscheidung kann jetzt erfolgen. Die Entscheidung zu treffen ist aber nicht gleichbedeutend damit, die Entscheidung auszugeben! Das darf natürlich nicht heute passieren, denn wenn Du es heute machst, guckst Du ja auf den Quantencomputer (Du kannst nicht messen ohne das Quantensystem zu beeinflussen) somit würdest Du den Quantencomputer beeinflussen wenn Du ihn fragst, ob jemand zugeguckt hast.

Aber Du kannst in 100 Jahren hingehen, nachgucken, ob in den 100 Jahren jemand zugeguckt hat (außer Dir). Das interessante dabei ist, das Quantensystem weiß das schon heute, also nicht erst, wenn da jemand zuguckt. Ein Quantensystem weiss also, ob auf einer Autobahn ein Auto kommt oder nicht (z. B. weil die Autobahn niemals ans Straßennetz angekoppelt wird). Wenn Du wissen willst, dass niemals ein Auto kommt, musst Du aber unendlich lange warten.

Den Beweis habe ich irgendwo mal gelesen. Glaub mir bitte, der war so abgefahren, dass ich mir das nicht merken konnte, aber ich habe mir gemerkt, dass es so ist, und das leuchtet mir auch ein. Nochmals:

Du selber wirst dieses Ergebnis niemals sehen! Du kannst nicht nachsehen und fragen "kommt da jemals ein Auto", Du kannst nur nachsehen und wirst erfahren "bisher war kein Auto da". Das ändert aber nichts daran, dass das Quantensystem bei geeigneter Konstruktion diese Information nicht trotzdem wissen kann.

Das ist beim Quantensystem übrigens unerheblich, denn technisch ist es dasselbe wie das Elektron, das weiss, wie es sich beim Doppelspalt verhalten muss, obwohl es das nicht wissen kann.

> > Diese Überzeugung kommt
> > durch den Tunneleffekt. Quantensysteme sind in der Lage, Lösungen zu
> > (er)finden, für die es keinen Algorithmus im herkömmlichen Sinn (für
> > eine Turingmaschine) gibt. Trotzdem finden sie eine passende Lösung,
> > sie liefern also sozusagen einen Geistesblitz, ohne dass es
> > eigentlich einen Lösungsweg dafür gab.
>
> Auch ein Quantencomputer kann keine unlösbaren Probleme lösen.

Das habe ich nicht behauptet. Ich habe behauptet, das Quantensystem kann mit einem Algorithmus, in dessen klassischen Lösungshorizont das Ergebnis nicht liegt, trotzdem zu dem Ergebnis kommt. Kann, nicht muss! Mit demselben Algorithmus wirst Du auf einer Turingmaschine niemals eine Lösung bekommen (auch nicht in unendlicher Zeit) da der Algorithmus die Lösung nicht liefern kann.

So gesehen liefert - vom klassischen Algorithmusgedanken - die Turingmaschine die korrekte Interpretation (in der Logik: Bottom, also die Nichtterminierung), währen das Quantensystem nach wenigen Sekdunden die Lösung rausrotzt, die aber so gesehen gar nicht im Algorithmus steckt.

Das kann die Turingmaschine nicht, weil sie deterministisch arbeitet. Die Quantencomputer haben diese Beschränkung nicht. Sie unterliegen Gödel nicht, weil Quanten Gödel nicht unterliegen. Wäre auch schlimm, weil dann wäre die Welt widersprüchlich oder unvollständig.

> > Die Lösung kann aber von
> > einer Turingmaschine niemals errechnet werden, da sich die Lösung
> > überhaupt nicht im "Berechnungshorizont" der Maschine befinden muss.
>
> Ein Problem ist berechenbar, genau dann, wenn es auf einer
> Turing-Maschine berechenbar ist.

Stimmt! Die Quantencomputer berechnen die Lösung dafür auch nicht. Sie (er)finden sie. Sie können die Lösung nicht berechnen, aber sie können beispielsweise in endlicher Zeit entscheiden, dass ein Problem in unendlicher Zeit nicht berechenbar ist. Das geht übrigens nicht für alle klassischen Probleme der Nichtentscheidbarkeit.

Ich denke(!), Quantencomputer werden letztendlich klären, ob PV = NP oder nicht! Das ist ein Nichtentscheidungsproblem, welches von klassischen Computern nicht berechnet werden kann. Im Fall NP=P wissen wir dann, wir waren zu dumm, aber Du hast Recht. Im Fall von NP!=P wäre dann klar, dass Quantencomputer etwas berechnen können, das Turingmaschinen nicht berechnen können (ich hätte Recht).

> > Wir haben also zwei Gründe, warum eine Turingmaschine niemals ein
> > Quantensystem berechnen kann, nicht einmal ansatzweise:
>
> Es geht auch nicht um ein Quantensystem - genausowenig wie um ein
> Sonnensystem - sondern um Computer. Worauf diese basieren ist egal.

Nein. Du sprichtst von Automaten, ich von Computern. Nochmals:

Auf einem Computer läuft ein Algorithmus ab. Ein Algorithmus muss nicht deterministisch sein (eine Hausfrau, die einen Kuchen backt, kann dies niemals zweimal gleich machen, trotzdem ist ein Kuchenrezept ein Algorithmus, und die Hausfraus sozusagen der Computer der diesen Algorithmus abarbeitet).

Du sagst aber, ein Computer ist beschränkt auf die endlichen (deterministischen) Automaten. Dieser Meinung bin ich (und anscheinend auch andere) nicht.

Was Du natürlich schreibst ist richtig, bezogen aber nur auf die deterministischen endlichen Automaten (die streng genommen nicht einmal Turingmaschinen sind).

> > Quantenrechner können daneben natürlich auch alle klassischen
> > Algorithmen berechnen.Das ist auch logisch. Wir, und auch
> > Turingmaschinen (nachdem sie konstruiert wurden), basieren auf
> > Quanten. Turingmaschinen sind also eine bestimmte extrem beschränkte
> > Klasse der Quantenrechner. Aber es gibt eben bestimmte
> > Quantenrechner, die nicht mehr zu Turingmaschinen äquivalent sind.
>
> Ein Computer kann immer nur lösbare Aufgaben lösen. Innerhalb jedes

Wo steht das?

Ein Computer verfolgt einen Algorithmus. Mehr erwarte ich nicht. Ob das Ergebnis korrekt ist oder nicht das steht auf einem vollkommen anderen Blatt. Lösbarkeitsprobleme sind nur eine Klasse von Algorithmen. Vielleicht will ich keine Lösung, vielleicht will ich nur einen Algorithmus, z. B. zur Lichtsteuerung des Hauses. Der Computer soll da gar nicht zu einer Lösung kommen, ich will dass mein Licht immer ordentlich gedimmt ist, wie ich es will.

Meine Computer sollen das irgendwann mal leisten. Ich will aber keine Lösung, die Lösung kann nur bedeuten, der Computer sperrt mich aus meinem Haus aus, damit er das Licht abdrehen kann und damit die Lösung des "Problems" Lichtsteuerung hat. Soviel auch zu Neugents und CA ;)

> hinreichend komplexen Regelwerkes lassen sich Aussagen formulieren,
> deren Richtigkeit weder bewiesen noch widerlegt werden können. Das

Komisch, Quantensysteme werden genau das leisten, so lange das Regelwerk endlich ist. Du musst das Regelwerk nur im Quantencomputer implementieren, dank Vielweltenansatz wird der Quantenrechner in endlicher Zeit zu einem Ergebnis kommen (außer der Algorithmus hat wirklich keine Lösung, ist also wirklich unentscheidbar). Aber - und das ist das interessante - Du kannst dann wahrscheinlich den Quantencomputer in endlicher Zeit fragen, ob das Problem lösbar ist.

> ist ein logisches Problem, das mit Physik und Quanten rein garnichts
> zu tun hat und das durch diese deshalb auch nicht beeeinflusst wird.

Du denkst falsch. Quanten sind nicht logisch. Sie haben nichts mit Logik zu tun. Hätten sie das, unterliegt unsere Welt dem Unvollständigkeitssatz von Gödel. Dem ist nicht so. Also sind die Quanten niemals Formal. Logik ist aber ein Formalismus. Quanten unterliegen solchen Formalismen nicht.

Und genau das kannst Du in Quantencomputern umsetzen! (Das muss geeignet implementiert werden, und bis wir in der Lage sind, zu begreifen, wie das geht, wird es noch lange dauern. Aber das geht, das muss gehen, denn Quanten sind Quanten. Vielleicht sind wir zu Dumm das je zu begreifen, das liegt aber nur an unserer Beschränktheit, nicht an den Quantencomputern.)

> Quantencomputer können vielleicht einmal die Grenzen dessen, was
> praktisch berechenbar ist, erweitern, auflösen werden sie diese
> Grenzen nie.

Das habe ich auch nicht behauptet. Auch für Quantencomputer gibt es eng gestreckte Grenzen. Sie können nicht alles. Aber sie können mehr als Turingmaschinen. Und damit mehr als Digitalcomputer.

-Tino
PS: Warum ich davon ausgehe hat noch einen anderen Grund: Ich weigere mich, zu akzeptieren, dass ein Computer ein menschliches Gehirn simulieren kann (emulieren in bestimmten Grenzen vielleicht, aber niemals simulieren). Mit Quantencomputern habe ich damit aber kein Problem, denn Quantencomputer unterliegen Gödel nicht. Ich will einfach nicht Gödel unterliegen. Reiner Egoismus ;)