Verblüfft von Rices Theorem

37

Zusammenfassung: Nach dem Satz von Rice ist alles unmöglich. Und doch mache ich diese vermeintlich unmöglichen Sachen die ganze Zeit!


Natürlich sagt der Satz von Rice nicht einfach "alles ist unmöglich". Es heißt etwas ganz Konkretes: "Jede Eigenschaft eines Computerprogramms ist nicht berechenbar."

(Wenn Sie Haare teilen möchten, ist jede "nicht-triviale" Eigenschaft, dh Eigenschaften, die alle Programme oder keine Programme besitzen, trivial berechenbar. Jede andere Eigenschaft ist jedoch nicht berechenbar.)

Das sagt der Satz oder scheint es zu sagen. Und vermutlich haben eine große Anzahl sehr kluger Leute die Richtigkeit dieses Theorems sorgfältig überprüft. Aber es scheint der Logik völlig zu trotzen! Es gibt zahlreiche Eigenschaften von Programmen, deren Berechnung trivial ist !! Beispielsweise:

  • Wie viele Schritte führt ein Programm aus, bevor es anhält? Zu entscheiden, ob diese Zahl endlich oder unendlich ist, ist genau das nicht berechenbare Halteproblem. Zu entscheiden, ob diese Zahl größer oder kleiner als ein endliches ist, ist trivial! Führen Sie das Programm einfach in bis zu Schritten aus und prüfen Sie, ob es anhält oder nicht. Einfach!nn

  • In ähnlicher Weise verwendet das Programm in seinen ersten Ausführungsschritten mehr oder weniger als Speichereinheiten ? Trivial berechenbar.nm

  • Erwähnt der Programmtext eine Variable mit dem Namen ? Eine triviale Textanalyse wird die Antwort aufdecken.k

  • Ruft das Programm den Befehl ? Scannen Sie den Programmtext erneut nach diesem Befehlsnamen.σ

Ich kann viele Eigenschaften sehen, die auch nicht berechenbar aussehen. ZB wie viele Ergänzungen führt ein vollständiger Programmlauf durch? Das ist fast dasselbe wie die Frage, wie viele Schritte das Programm ausführt, was praktisch das Problem des Anhaltens ist. Aber es sieht so aus, als gäbe es eine Menge Programmeigenschaften, die sehr, sehr einfach zu berechnen sind. Und doch besteht der Satz von Rice darauf, dass keiner von ihnen berechenbar ist.

Was vermisse ich hier?

MathematicalOrchid
quelle
8
"Nach dem Satz von Rice ist alles unmöglich." - Nein. "Jede Eigenschaft eines Computerprogramms ist nicht berechenbar." - Nein. Sie sind jedoch nicht allein: Die meisten Studenten stoßen auf dieses Missverständnis.
Raphael

Antworten:

36

Für die Zwecke dieser Diskussion ist ein "Programm" ein Teil des Codes, der immer eine Ganzzahl als Eingabe verwendet und entweder für immer ausgeführt wird oder eine Ganzzahl zurückgibt. Wir sagen, dass zwei Programme und im Wesentlichen gleich sind, wenn sie dieselbe Funktion berechnen, dh für jede Zahl entweder beide und ewig laufen oder beide enden und dieselbe Zahl ausgeben.fgnf(n)g(n)

Eine Erweiterungseigenschaft von Programmen ist eine Eigenschaft , die die Erweiterungsgleichheit respektiert, dh wenn und in Bezug auf die Erweiterung gleich sind, haben sie entweder beide die Eigenschaft oder beide haben sie nicht.PfgP

Hier sind einige Beispiele von nicht -extensional Eigenschaften:

  1. Das Programm stoppt innerhalb von Schritten. (Wir können ein Programm jederzeit in ein gleiches Programm ändern, das länger läuft.)n
  2. Das Programm verwendet innerhalb der ersten Ausführungsschritte weniger als Speicherzellen . (Wir können ein Programm jederzeit in ein gleiches Programm ändern, damit es ohne guten Grund Speicherplatz beansprucht.)nm
  3. Der Programmtext erwähnt eine Variable mit dem Namen k. (Wir können Variablen umbenennen.)
  4. Ruft das Programm den Befehl . Dies mag ein bisschen davon abhängen, was ist, aber wenn es sich um etwas handelt, das auf irgendeine Weise simuliert werden kann, dann können wir ausweichen und haben immer noch ein Programm, das weitgehend dem Original entspricht.σσσ

Ich bin sicher, Sie haben bemerkt, dass ich genau Ihre angeblichen Gegenbeispiele zu Rices Theorem aufgelistet habe, die besagen:

Theorem (Rice): Eine berechenbare Erweiterungseigenschaft von Programmen gilt entweder für alle Programme oder für keine.

Es gibt einen anderen Weg, dies zu erklären: Sie müssen zwischen einem Programm und der Funktion, die es berechnet, unterscheiden. Viele verschiedene Programme berechnen die gleiche Funktion (sie sind alle weitgehend gleich). Beim Satz von Rice geht es um Eigenschaften von Funktionen, nicht um Eigenschaften von Programmen, die sie berechnen.

Andrej Bauer
quelle
Ich kann diese Antwort nicht bekommen. (Entschuldigung, wenn ich dasselbe frage, wäre aber gut, diesen Punkt zu klären). Es sagt , dass Sie diese Programme durch Änderung ihrer ändern können Syntax eine extensionale zu bekommen gleichwertig , aber wie diejenigen sind extensional äquivalent in erster Linie überprüfen? Sie können ein Programm nicht zum Vergleichen verwenden, wenn diese Programmfunktionen im Allgemeinen über beide Eigenschaften verfügen. Wenn Sie also "Ändern" sagen, ist dies meines Erachtens möglich, da es sich um einfache Beispiele handelt IDE dafür "? ..) Ich denke, einmal geändert, kann man im Allgemeinen nicht überprüfen , vielleicht hält Rice.
Hernan_eche
1
Im Allgemeinen überprüfen Sie, ob zwei bestimmte Programme weitgehend gleich sind, indem Sie nachweisen, dass dies der Fall ist. Erheben Sie Einwände gegen die Tatsache, dass für alle ganzen Zahlen gilt, obwohl ein Computer diese Gleichheit nicht für alle Werte "prüfen" kann? Hoffentlich nicht. Es gibt einen Unterschied zwischen dem Schreiben eines Programms, das einen Booleschen Wert berechnet, und dem Nachweis, dass eine bestimmte Aussage einen bestimmten Wahrheitswert hat. Es gibt Dinge, die wir beweisen können, aber nicht berechnen können (z. B. die Tatsache, dass zwei bestimmte Programme weitgehend gleich sind oder dass die Addition kommutativ ist). n+m=m+n
Andrej Bauer
Außerdem begehen Sie einen merkwürdigen Schritt in Ihrer Argumentation: Da die Gleichheit der Ausdehnungen nicht entscheidbar ist, könnte der Satz von Rice falsch sein. Wieso das? Und nur weil Extensionsgleichheit unentscheidbar ist, heißt das nicht, dass es keine Fälle gibt, über die wir entscheiden können. Die, die ich erwähnt habe, können wir entscheiden.
Andrej Bauer
36

Grundlegendes Missverständnis:

Jede Eigenschaft eines Computerprogramms ist nicht berechenbar

Darüber spricht der Satz von Rice nicht. Es geht um Eigenschaften von Funktionen und darum, dass die Menge der Programme, die diese Funktion berechnen, nicht bestimmbar ist. Formal ist die Menge gegebenPRE

{MfMP}

ist nicht entscheidbar. Für die von Ihnen genannten Eigenschaften finden Sie kein geeignetes für das die Programmgruppe diese Form hat. Einige Programme für eine Funktion verfügen möglicherweise über die Eigenschaft, während andere (für dieselbe Funktion) möglicherweise nicht über die Eigenschaft verfügen. Sehen Sie hier einige Beispiele.P

Der Satz von Rice befasst sich mit semantischen Eigenschaften (Eigenschaften der von einem Programm berechneten Funktion , z. B. Domäne oder Wertebereich). Sie beziehen sich auf syntaktische Eigenschaften (Eigenschaften des Programms , z. B. Laufzeit oder wie viele Variablen verwendet werden).

Für syntaktische Eigenschaften scheint nicht viel bekannt zu sein; siehe diese Frage .

Raphael
quelle
1
Ich habe mich nach ungefähr dem ersten Satz verlaufen. Es tut uns leid. Kann jemand den Unterschied zwischen einer semantischen und einer syntaktischen Eigenschaft erläutern?
MathematicalOrchid
@MathematicalOrchid: Sie können diesen Satz ignorieren. Der erste Absatz enthält alle Informationen, die Sie benötigen. Ich werde sowieso näher darauf eingehen.
Raphael
2
Semantik = Was macht das Programm? Syntaktisch = wie das Programm aussieht.
Reinierpost