Beiträge von _gerald_

Angenommen es gaebe nur abzaehlbar viele solche Funktionen. Nennen wir die Menge dieser Funktionen A und die Bijektion von A nach [tex='\mathbb{N}'][/tex]

nennen wir h. Wir konstruieren nun eine Funktion g von den nat. Zahlen nach {0,1}, welche nicht in A liegen kann.

g(n) = 1 falls h(n)[n] = 0
= 0 sonst.

Angenommen es gibt ein m, sodass h(m) = g. Schauen wir uns dann g(m) an:

Fall 1: g(m) = 1. Dann ist aber h(m)[m] = 0, somit gilt g != h(m)
Fall 2: g(m) = 0. Dann gilt h(m)[m] = 1, somit gilt g != h(m)

Das ist nur der Satz von Cantor in 0-1 Folgen ausgedrueckt. Das selbe kannst mit der Potenzmenge machen.

Zitat von Adok

Nur finde ich nicht, dass wir uns auf diese Ebene einlassen müssen, weil ja auch umgekehrt jede mathematische Funktion als Algorithmus ausgedrückt werden kann.

Es gibt ueberabzaehlbar viele Funktionen [tex='f : \mathbb{N} \rightarrow \{0,1\}'][/tex]

, jedoch bei den (in der Komplexitaetstheorie betrachteten) Maschinenmodellen nur abzaehlbar viele Algorithmen...