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(unten 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, so das 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 :-(

[img]http://mokrates.de/cgi-bin/texstring?f_n(3)[/img]

Mo

Alter, Mo, geh schlafen!

Aber Du! Also: ich hab hier noch ein Bier…

Mo

[img]http://mokrates.de/cgi-bin/texstring?f_n(3)[/img]

Mo

genau Mo, so hatte ich das gemeint, ich konnte nur nicht mit latex arbeiten weil nach ein paar von diesen hier "[img]http://mokrates.de/cgi-bin/texstring?f_n(n)n%3E%3D1[/img]" kam fehlermeldung; maximal 4 bildchen….

huch, sorry wollte eigentlich die verbesserten latex-ausdruecke nehmen, ging irgendwie nicht sry wegen doppelpost

vielleicht hilft dir diese Seite weiter,
da wird das anscheinend für f{n}(n)+1 gezeigt (was aber deutlich einfacher aussieht)

http://www.joergresag.privat.t-online.de/mybk3htm/chap23.htm

jo an der funktion musste man es eine aufgabe vorher zeigen.
mein beweis war hier ohne kantor:

behauptung g mit g_n(n)=n+1 ist abzaehlbar, dann ist g in der aufzaehlung der f_n(n) enthalten, somit muss ein m existieren,
dass gilt: g(m)=f_m(m), aber nach definition von g ist g an m gerade g(m)=f_m(m)+1 also nicht abzaehlbar.

fuerchte das wird nix mit dem uebungsblatt :(

hmbl natuerlich abzaehlbar und berechenbar durcheinandergewuerfelt, egal, ich knobel weiter

keiner ne idee ? schnueff
vielleicht kleiner ansatz wenigstens damits nen
teil der punkte gibt ? buedde buedde

so nach einer durchzechten nacht hab ich doch noch was hingekriegt. ich schreibs mal fuer alle die vielleicht dasselbe
problem haben und wie ich nichts vernuenftiges er-googeln konnten:

grundidee:


wäre g berechenbar, dann auch h(n):=g(floor(sqrt(n-1))+1. also gibt es ein

i mit h=f_i. nun müsste einerseits gelten:

h(i^2+1)=g(floor(sqrt(i^2+1-1))+1=g(i)+1,

andererseits aber auch:

h(i^2+1)=f_i(i^2+1)=g(i),

was aber nicht möglich ist.


noch bissl ausformulieren auf die saetze und definitionen beziehen und fertig ist der kuchen