| 1=0! |
Diagonalisierungsargument.
Hallo,
Sie f eine 1-universelle Funktion für F(REK).
Dann kann man g definieren durch
g(x)=f(x,x)+1 falls f(x,x) definiert und g(x)=0 sonst.
Nun gilt offensichtlich g(e)=f(e,e)+1>f(e,e) , was ein Widerspruch zur Universalität ist und somit g nicht rekursiv sein kann.
Bis hier hin ist es mir klar.
Jetzt wird hierraus aber auch gefolgert dass {x:f(x,x) definiert} nicht rekursiv ist. Warum sollte das gelten?
mfg
1=0! |
