Matheproblem bissl mit Informatik angehaucht...

Neue Frage »

Vollwurst Auf diesen Beitrag antworten »
Matheproblem bissl mit Informatik angehaucht...
Hi,

zunaechst mal zur Bezeichnung: mit "[n]" meine ich immer den niedrigen index unten rechts, z.b. f[n](n) fuer n=3 ist als f(unte 3) 3 an der Stelle 3 zu lesen.

Also: Sei (f[n]) n>=1 eine Abzaehlung aller berechenbarer, totaler Funktionen. Zeigen oder widerlegen Sie: Die Funktion g mit g(n)= f[n](n²+1) ist nicht berechenbar. Sie duerfen annehmen dass n² und floor(sqrt(n)) turing-berechenbar sind.

Was mir bisher eingefallen ist:
Abzaehlbar natuerlich das klassische Stichwort fuer Cantor. Also Funktionen geschickt hingeschrieben, und dann Beweis durch Widerspruch versucht:

Annahme: g ist nicht berechenbar!
Ist dies der Fall, so darf sich g nicht aus den f[n](n) konstruieren lassen da das ja die Abzhälung aller berechenbarer, totaler Funktionen ist.

f[1](1) f[2](1) f[3](1) .... f[n](1)
f[1](2) f[2](2) ....
....
....
f[1](n) .....

nun picke ich aber aus der i-ten Zeile das i²+1 te
Element raus, also z.b. f[1](3), f[2](5), f[3](10) etc womit ich genau g konstruieren wuerde was g berechenbar bzw turing-berechenbar macht.

Aber irgendwie fehlt da noch die Richtige darstellung was diese heisse Luft in nen mathematischen Beweis verwandelt, vor allem macht
mich stutzig dass ich die hilfeangabe nicht brauche dass n² und floor(...) turing-berechenbar sind :-((
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »