Ich habe mal eine Frage zum Halteproblem. (http://www.cs.odu.edu/~toida/nerzic/390teched/comput…)
Wenn G existiert, dann existiert auch H. H existiert gemäß der Beweiskizze aber nicht. ☇
Wenn G nicht existiert, dann ist die Bewiskizze aber falsch und H könnte existieren.
→ Die Beweisführung ist falsch und H könnte existieren. Ob G aber existiert, weiß man deshalb ebenfalls nicht.
Ich habe mal eine Frage zum Halteproblem.
(http://www.cs.odu.edu/~toida/nerzic/390teched/comput…)
OK, das ist ein wenig kurz gefasst, eigentlich muß für die Einzelschritte gezeigt werden, dass die alle turingberechenbar sind, aber intuitiv ist das klar.
Wenn G existiert, dann existiert auch H. H existiert gemäß der
Beweiskizze aber nicht. ☇
Wenn G nicht existiert, dann ist die Bewiskizze aber falsch
und H könnte existieren.
→ Die Beweisführung ist falsch und H könnte
existieren. Ob G aber existiert, weiß man deshalb
ebenfalls nicht.
Was ist G, was ist H? In der Quelle ist nur von T, T_m und T_c die Rede.
G ist T_m. H ist T.
G ist T_m. H ist T.
Also Du meinst Wenn T_m existiert, dann existiert auch T. T existiert gemäß der
Beweiskizze aber nicht. ☇
Wenn T_m nicht existiert, dann ist die Bewiskizze aber falsch
und T könnte existieren.
→ Die Beweisführung ist falsch und T könnte
existieren. Ob T_m aber existiert, weiß man deshalb
ebenfalls nicht.
Mein Kommentar dazu:
Wieso sollte T existieren, wenn T_m existiert? Dafür müsste gezeigt werden, dass aus T_m eine Maschine, die das Halteproblem löst, konstruiert werden kann. Aber angenommen es wäre so (Wenn ex. T_m -> ex. T.).
T existiert nacht Beweis nicht: das ist korrekt.
Wenn T_m nicht existiert, dann ist die Bewiskizze aber falsch
und T könnte existieren: klassischer Fehlschluß aus A -> B zu folgern, dass nicht B, wenn nicht A (es gilt nur: wenn nicht B, dann nicht A).
Die Beweisführung ist falsch und T könnte
existieren.: was sollte das beudeten „T könnte existieren“? Modallogisch: T existiert. Ob T nun existiert oder nicht wäre damit nicht belegt.
Also: klassischer Fehlschluß mit dem Konditional (->:wink:.
beste Grüße
NNe
Könnte existieren heißt das man es nicht weiß, ob es existiert.
Könnte existieren heißt das man es nicht weiß, ob es
existiert.
Genau und mit der Aussage ist noch kein Widerspruch gezeigt.
Unabhängig davon, ob T existiert, ist die Beweisführung aber falsch.
T existiert → Beweisführung falsch
T existiert nicht → T_m existiert nicht → Beweisführung falsch
Hi!
Wenn bei einem indirekten Beweis etwas falsches vorkommt, heißt das nicht, das der gesamte Beweis falsch ist.
Formal: (NICHT A => Falsch) => A
D. h. Man sieht, dass aus NICHT A etwas falsches – etwa ein Widerspruch wie „B UND (NICHT B)“ – folgt. Es gibt klassisch nur die Möglichkeiten A und NICHT A. NICHT A kann nicht sein, also bleibt nur noch A. Dann hat man A bewiesen.
In diesem Fall ist A die Aussage „Eine Turingmaschine T, die das Halteproblem löst, existiert nicht“. NICHT A, die Annahme sie existiere doch, führt zu einem Widerspruch - demnach ist A wahr.
Also:
(NICHT „T existiert nicht“ => Falsch) => T existiert nicht
(ungerade Anzahl an nicht bzw. falsch)
Und wie kommst du bitte darauf?
So wird das nichts. Schreib mal die These auf, die Du beweisen willst (Satz, Theorem, Aussage). Dann führ den Beweis durch.
Der Beweis des Halteproblems ist ein Beweis durch Widerspruch:
Annahme T existiert -> Widerspruch.
-> T existiert nicht (und nicht: „Beweisführungt falsch“ - die Beweisführung ist nämlich korrekt: es handelt sich um einen Beweis durch Widerspruch.)
Daraus , dass T nicht existiert kannst Du erstmal nicht folgern, dass eine Maschine T_m` nicht existieren kann, die genau die Aufgaben löst, die T_m löst. Aber sei mal zugestanden Du hättest solch einen Beweis und es gelte
T existiert nicht -> T_m existiert nicht.
Daraus folgt nicht, dass irgendweine „Beweisführung“ falsch ist? Welche überhaupt? Hier hast Du gar keinen Widersruch abgeleitet.
[Schau Dir bitte in einem Logiklehrbuch die Ausführungen zum Beweis durch Widerspruch und die Probleme bei naivem Umgang mit dem materialen Konditional an. Z.B. Eike von Savigny: Grundkurs im logischen Schließen. oder Jon Barwise and John Etchemendy: The language of first-order logic.]
Übrigens ist die Aussage, dass eine Beweisführung falsch sei, sehr salopp. Man macht das zwar, aber hier kommst Du damit in Verwirrung, weil es sich streng genommen um eine Aussage zweiter Ordnung handelt und man eigentlich sagen muß: Beweisführungen sind weder wahr oder falsch, sondern nur korrekt oder nicht. Wahr oder falsch können nur Aussagen sein (z.B. Annahmen).]
Es fehlt also zu Deiner Behauptung auf jeden Fall noch der Beweis, dass aus T_m existiert nicht ein Widerspruch abgeleitet werden kann.
Die Verknüpfung A => B ist definiert über die vier Fälle:
(Falsch => Wahr) ist Wahr
(Falsch => Falsch) ist Wahr
(Wahr => Falsch) ist Falsch
(Wahr => Wahr) ist Wahr
(A => B) ist also gleichbedeutend mit „(NICHT A) oder B“.
Damit die aus logischen Schlüssen über Turingmaschinen entstandene (also wahre) Aussage
(NICHT „T existiert nicht“ => Falsch)
wahr sein kann, muss also der Teil links vom „=>“, nämlich
(NICHT „T existiert nicht“)
falsch sein.
Sorry da kann ich nicht helfen
Ist das also ein „bitweises ODER“?
Die Operation „=>“ ist nicht symmetrisch, d. h.
gilt A=>B muss nicht unbedingt B=>A gelten; das unterschiedet sie vom ODER.
Entschuldigung, die Zeile
(Falsch => Falsch) ist Wahr
hab ich übersehen.
Also kein bitweiser Operator.
Sondern:
01=1
00=1
10=0
11=1
Und
(NICHT „T existiert nicht“ => Falsch) => T existiert nicht
entspricht dann:
10=0
Nur wie kommst du darauf, dass hier diese Regel angewendet werden kann?
Wie das ist wirklich der einzige Unterschied? Obwohl ich mich doch eigentlich versehen habe?
Die Verknüpfungen „=>“ und ODER sind verschieden allein nach Definition ihrer Verknüpfungstabelle. Man kann sie höchstens mit Hilfe von NICHT aus den jeweils anderem „zusammenbauen“:
(A=>(NICHT B))=>((NICHT B)=>A)
ist gleichwerig zu
A ODER B.
(NICHT A) ODER B
ist gleichwertig zu
A=>B.
Nehmen wir mal die Aussage
(A UND (A=>B)) => B
Für sie gilt die Wahrheitstafel:
A=Wahr A=Falsch
B=Wahr Wahr Wahr
B=Falsch Wahr Wahr
Sie ist also für alle Belegungen der vorkommenden Aussagesymbole wahr. Aus solchen allgemeingültigen Aussagen kann man ein Beweisprinzip ableiten: Gilt A und lässt sich B aus A herleiten (A=>B), dann ist damit B bewiesen. „(A UND (A=>B)) => B“ ist also das Prinzip eines direkten Beweises.
Noch ein Beispiel:
((A ODER B) UND (A=>C) UND (B=>C)) => C
Ist für alle Wahr-Falsch-Belegungen von A, B und C wahr (allgemeingültig). Als Beweisprinzip: Wenn immer mindestens einer von zwei Fällen (A ODER B) gilt, und kann ich sowohl aus A als auch aus B unser C ableiten, d. h."(A=>C) UND (B=>C)", so ist C damit bewiesen. (Prinzip des Beweises durch Fallunterscheidung)
Nun zu unserer Aussage
(NICHT A => Falsch) => A
Auch sie ist für alle Belegungen der vorkommenden Aussagesymbole (hier nur die Fälle A=Wahr und A=Falsch) wahr (allgemeingültig). D. h. ohne vorher zu wissen, ob A=(Eine Turingmaschine T existiert nicht) zutrifft, kann ich allein durch die Feststellung „Aus der Annahme sie existiere (NICHT A) folgt ein Widerspruch (d. h. Falsch)“ schlussfolgern, dass A gilt. Das Beweisprinzip ist es, aus NICHT A einen Widerspruch abzuleiten, um A zu beweisen (Reductio ad absurdum).
Ich habe mich jetzt ein wenig mit Aussagenlogik beschäftigt.
T = H
A = nicht(T)
T_m = G
Wenn man davon ausgeht, dass folgendes gilt:
(NICHT A => Falsch) => A
Dann geht man davon, aus dass „nicht H“ nicht gilt und daher das Gegenteil, nämlich A gelten muss. Also keine Maschiene existiert, die das Halteproblem lösen kann.
Ich meine aber folgendes:
T_m => T;
NICHT T => NICHT T_m;
T_m => (T => Falsch) => NICHT T
=> NICHT T => NICHT T_m; ☇
Fazit:
Aussagenlogik ist eine tolle Sache. So kann man viel besser sagen, was man meint.
Also: klassischer Fehlschluß mit dem Konditional (->:wink:.
Stimmt. Das habe ich ganz übersehen, dass da noch eine Aussage fehlt.
Wenn du davon ausgehst, dass meine Argumentation stimmt, dann könntest du dir die Aussage aber auch denken, dass ich von der auch noch ausgehe.