Re: nicht-berechenbare Mengen
Verfasst: 17. Sep 2017, 10:18
Ich denke, wir sind (und ich war) hier sprachlich unpräzise.
Eine Aussage ist beweisbar, wenn innerhalb eines Axiomensystems ein endlicher Beweis für diese Aussage existiert.
Eine Zahl ist berechenbar, wenn ein endlicher und in endlich vielen Schritten terminierender Algorithmus (eine Turingmaschine) existiert, der diese Zahl als Ergebnis ausgibt.
D.h. dass sich Beweisbarkeit auf Aussagen und Berechenbarkeit auf Zahlen (u.a. mathematische Objekte) bezieht. Damit sind beide Begriffe m.E. nicht identisch, sie sind jedoch verwandt und für bestimmte Probleme unter bestimmten Voraussetzungen äquivalent.
Es gibt jedoch auch Fälle, anhand derer man explizit erkennt, dass diese Begriffe i.A. nicht identisch sind. Z.B. kann man in ZFC die Existenz bestimmter Zahlen und Objekte beweisen, ohne sie berechnen bzw. konstruieren zu können. Man kann sogar beweisen, dass letzteres nicht funktioniert: es gibt überabzählbar viele reelle Zahlen jedoch nur abzählbar viele Turimgmaschinen mit Input; deswegen können nicht alle reellen Zahlen berechenbar sein; umgekehrt: "fast alle" reellen Zahlen sind nicht-berechenbar.
Ein explizites Beispiel für eine nicht-berechenbare Zahl ist die Chaitinsche Konstante, die beweisbar existiert jedoch ebenso beweisbar nicht berechenbar ist.
Eine Aussage ist beweisbar, wenn innerhalb eines Axiomensystems ein endlicher Beweis für diese Aussage existiert.
Eine Zahl ist berechenbar, wenn ein endlicher und in endlich vielen Schritten terminierender Algorithmus (eine Turingmaschine) existiert, der diese Zahl als Ergebnis ausgibt.
D.h. dass sich Beweisbarkeit auf Aussagen und Berechenbarkeit auf Zahlen (u.a. mathematische Objekte) bezieht. Damit sind beide Begriffe m.E. nicht identisch, sie sind jedoch verwandt und für bestimmte Probleme unter bestimmten Voraussetzungen äquivalent.
Es gibt jedoch auch Fälle, anhand derer man explizit erkennt, dass diese Begriffe i.A. nicht identisch sind. Z.B. kann man in ZFC die Existenz bestimmter Zahlen und Objekte beweisen, ohne sie berechnen bzw. konstruieren zu können. Man kann sogar beweisen, dass letzteres nicht funktioniert: es gibt überabzählbar viele reelle Zahlen jedoch nur abzählbar viele Turimgmaschinen mit Input; deswegen können nicht alle reellen Zahlen berechenbar sein; umgekehrt: "fast alle" reellen Zahlen sind nicht-berechenbar.
Ein explizites Beispiel für eine nicht-berechenbare Zahl ist die Chaitinsche Konstante, die beweisbar existiert jedoch ebenso beweisbar nicht berechenbar ist.