Konstruerbar funktion - Constructible function
I komplexitetsteorin är en tidskonstruerbar funktion en funktion f från naturliga tal till naturliga tal med den egenskapen att f ( n ) kan konstrueras från n av en Turing-maskin under tiden f ( n ). Syftet med en sådan definition är att utesluta funktioner som inte ger en övre gräns för körtiden för någon Turing -maskin.
Tidskonstruerbara definitioner
Det finns två olika definitioner av en tidskonstruerbar funktion. I den första definitionen kallas en funktion f tidskonstruerbar om det finns ett positivt heltal n 0 och Turing-maskin M som, med en sträng 1 n bestående av n en , stannar efter exakt f ( n ) steg för alla n ≥ n 0 . I den andra definitionen kallas en funktion f tidskonstruerbar om det finns en Turing-maskin M som, med en sträng 1 n , matar ut den binära representationen av f ( n ) i O ( f ( n )) -tiden (en enhetsrepresentation kan användas istället, eftersom de två kan omvandlas i O ( f ( n )) tid).
Det finns också en uppfattning om en helt tidskonstruerbar funktion. En funktion f kallas helt tidskonstruerbar om det finns en Turing-maskin M som, med tanke på en sträng 1 n bestående av n en , stannar efter exakt f ( n ) steg. Denna definition är något mindre allmän än de två första men för de flesta applikationer kan endera definitionen användas.
Rymdkonstruerbara definitioner
På liknande sätt, en funktion f är utrymmes constructible om det finns ett positivt heltal n 0 och en Turing maskin M som, givet en sträng 1 n bestående av n sådana, stannar efter att ha använt exakt f ( n ) celler för alla n ≥ n 0 . Ekvivalent, en funktion f är utrymmes constructible om det existerar en Turing maskin M som, givet en sträng 1 n bestående av n sådana, utmatar den binära (eller unär) representation av f ( n ), medan med användning av endast O ( f ( n )) Plats.
En funktion f är också fullt rymdkonstruerbar om det finns en Turing-maskin M som, med tanke på en sträng 1 n bestående av n en , stannar efter att ha använt exakt f ( n ) celler.
Exempel
Alla de vanliga funktionerna f ( n ) (som n , n k , 2 n ) är tids- och rymdkonstruerbara, så länge f ( n ) är minst cn för en konstant c > 0. Ingen funktion som är o ( n ) kan vara tidskonstruerbar såvida den inte så småningom är konstant, eftersom det inte finns tillräckligt med tid för att läsa hela ingången. Det är dock en rymdkonstruerbar funktion.
Ansökningar
Tidskonstruerbara funktioner används i resultat från komplexitetsteori, såsom tidshierarkinsatsen . De är viktiga eftersom tidshierarkinsatsen bygger på Turing -maskiner som måste bestämma i O ( f ( n )) -tiden om en algoritm har tagit mer än f ( n ) steg. Detta är naturligtvis omöjligt utan att kunna beräkna f ( n ) under den tiden. Sådana resultat är vanligtvis sanna för alla naturliga funktioner f men inte nödvändigtvis sanna för artificiellt konstruerade f . För att formulera dem exakt är det nödvändigt att ha en exakt definition för en naturlig funktion f för vilken satsen är sann. Tidskonstruerbara funktioner används ofta för att tillhandahålla en sådan definition.
Rymdkonstruerbara funktioner används på liknande sätt, till exempel i rymdhierarkinsatsen .
Denna artikel innehåller material från konstruerbart på PlanetMath , som är licensierat enligt Creative Commons Erkännande/Dela-Lika-licens .
