Bevis för att det inte går att "hoppa fram" i rekursiva formler?

edit: Vi gör om det här, ska gå rakt på sak. Tackar för övrigt dbshw nedan.

Vid formler för talserier så måste man ibland beräkna dem iterativt för att bestämma y(n).
Hur bevisar man att man måste beräkna en formel iterativt? Reserverar dessa bevis även för lösningar som skulle kunna ligga outside the box?

Jag förstår nog inte frågan riktigt, men bara för att en formel är definierad rekursivt behöver ju inte betyda att det måste beräknas iterativt; t.ex. i ditt exempel kan man få en sluten formel

y(n) = n(n+1)/2.

Min erfarenhet av rekursiva lösningar är att det är underbestämt så att det inte går att lösa på annat sätt. Detta är ju vanligt inom många olika grenar. Har man n variabler men bara n-1 ekvationer som beskriver systemet får man ju vackert iterera tills man får en konvergerande lösning. Jag var inte medveten om att det fanns ett mer formellt bevis än så. Skall följa tråden med intresse.

fick i gymnasiet lära mig att det fanns två sätt att räkna ut tal i talserier.

vissa talserier hade en generell formel där du direkt kunde applicera platsen i talserien för att få veta värdet på den specifika platsen.

andra var mer relativa och krävde att du hade de nödvändiga startvärdena, (typ y(1)=3), och sedan fick iterera fram tills du hade y(n), för formeln för värdet på plats n använde värdet på plats n-1 (som exempel).

och att beviset för rekursiva (det sistnämnda) var ju att du använde värden som finns tidigare i talserien. och de värdena får du fram genom att använda ännu tidigare värden, osv ända tills du kommer till den punkt där du faktiskt har värdet (ditt startvärde)

Vet inte om jag har ett bra svar på frågan, jag tror svaret är att det är ganska svårt att göra såna bevis, och det är förvånansvärt ofta det finns lösningar "outside the box". Men jag tror i alla fall att jag tar mig friheten att försöka specificera och formalisera frågeställningen, och jag hoppas att det kan kasta lite ljus över frågan.

Formaliseringen kommer att bygga på begreppet asymptotisk komplexitet.

Terminologin nedan har jag hittat på själv och skall inte betraktas som standard.

Första observationen är att man måste bestämma vad som är de primitiva operationerna man kan räkna med. Säg t.ex. att vi definerar funktionen f genom f(0) = 1, f(n) = 2*f(n-1), och frågar oss, kan vi beräkna f icke-iterativt? Svaret är förstås ja om vi "har en knapp på miniräknaren för 'upphöjt till'", ty då är bara f(n) = 2^n. Men om vi bara har en sketen miniräknare med de fyra räknesättet, så misstänker jag att svaret är "nej", och vi måste rekursera på nåt sätt (men notera att (övning för läsaren ) inte ens här är inte den "uppenbara" iterativa lösningen den snabbaste). Så svaret beror alltså på "vilka knappar vi har på miniräknaren", låt oss kalla operationer vi kan göra på vår miniräknare för primitiva operationer, och säga att vi kan utföra sådana operationer inom konstant tid.

Vad som "borde" vara primitiva operationer varierar nog från fall till fall, och det kan man säkert tvista om, men om man enas om vilka operationer så är primitiva, så tror jag följande definition fångar (åtminstone en aspekt) av det du vill få fram:

Säg att en funktion f(n) är icke-rekursivt beräkningsbar om det existerar en algoritm (en Turing-maskin om man så vill) som, givet att den får tillgång till "en miniräknare" som räknar ut de primitiva operationerna inom konstant tid, kan beräkna f(n) i konstant tid (det vill säga att tiden det tar är begränsad av en konstant oberoende av n, eller med andra ord, tiden det tar är O(1) (se ordo), när n går mot oändligheten).

Din fråga skulle då vara: hur bevisar man att en funktion inte är icke-rekursivt beräkningsbar?

Det här är säkert inte det enda sättet att formalisera frågan, men det är ett sätt, och jag hoppas att det är nåt man i alla fall kan bygga vidare på.

Till själva frågan då, spontant så tror jag att många rekursiva funktioner har "outside the box"-lösningar som är avsevärt snabbare än naiva rekursionslösningar. Och jag tror att det i allmänhet är ganska svårt att bevisa att snabba algoritmer inte existerar för ett visst problem (t.ex. handlar ju ett av Clay Institutes milleniumproblem om det, nämligen P=NP?). Men nån som kan sånt här får nog fylla i mer.

Är Gammafunktionen en "Out of the box"-lösning för fakultet i sådana fall? Den känns ju iaf inte så lätt att bara klura ut.

Man använder Galoisteori. Se t.ex. van der Put & Singer, "Galois Theory of Difference Equations."


Vet inte vad du menar med det. Det man bevisar är att det inte finns någon lösning som går att uttrycka med elementära operationer.