Funzione costruibile - Constructible function
Nella teoria della complessità , una funzione costruibile nel tempo è una funzione f da numeri naturali a numeri naturali con la proprietà che f ( n ) può essere costruita da n da una macchina di Turing nel tempo di ordine f ( n ). Lo scopo di tale definizione è escludere funzioni che non forniscono un limite superiore sul runtime di alcune macchine di Turing.
Definizioni costruibili nel tempo
Esistono due diverse definizioni di funzione costruibile nel tempo. Nella prima definizione, una funzione f si dice costruibile in tempo se esiste un intero positivo n 0 e macchina di Turing M che, data una stringa 1 n composta da n unità , si ferma dopo esattamente f ( n ) passi per tutti n ≥ n 0 . Nella seconda definizione, una funzione f è detta costruibile in tempo se esiste una macchina di Turing M che, data una stringa 1 n , restituisce la rappresentazione binaria di f ( n ) in tempo O ( f ( n )) (una rappresentazione unaria può essere usato invece, poiché i due possono essere interconvertiti in tempo O ( f ( n )).
C'è anche una nozione di funzione completamente costruibile nel tempo. Una funzione f si dice completamente costruibile in tempo se esiste una macchina di Turing M che, data una stringa 1 n composta da n unità , si ferma esattamente dopo f ( n ) passi. Questa definizione è leggermente meno generale delle prime due ma, per la maggior parte delle applicazioni, è possibile utilizzare entrambe le definizioni.
Definizioni costruibili dallo spazio
Allo stesso modo, una funzione f è costruibile nello spazio se esiste un intero positivo n 0 e una macchina di Turing M che, data una stringa 1 n composta da n unità , si arresta dopo aver utilizzato esattamente f ( n ) celle per tutti n ≥ n 0 . Equivalentemente, una funzione f è costruibile nello spazio se esiste una macchina di Turing M che, data una stringa 1 n composta da n unità , emette la rappresentazione binaria (o unaria) di f ( n ), mentre usa solo O ( f ( n )) spazio.
Inoltre, una funzione f è completamente costruibile nello spazio se esiste una macchina di Turing M che, data una stringa 1 n composta da n unità , si arresta dopo aver utilizzato esattamente f ( n ) celle.
Esempi
Tutte le funzioni comunemente usate f ( n ) (come n , n k , 2 n ) sono costruibili nel tempo e nello spazio, purché f ( n ) sia almeno cn per una costante c > 0. Nessuna funzione che sia o ( n ) può essere costruibile nel tempo a meno che non sia alla fine costante, poiché non c'è tempo sufficiente per leggere l'intero input. Tuttavia, è una funzione costruibile nello spazio.
Applicazioni
Le funzioni costruibili nel tempo sono utilizzate nei risultati della teoria della complessità come il teorema della gerarchia temporale . Sono importanti perché il teorema della gerarchia temporale si basa su macchine di Turing che devono determinare in tempo O ( f ( n )) se un algoritmo ha compiuto più di f ( n ) passi. Questo è, ovviamente, impossibile senza poter calcolare f ( n ) in quel tempo. Tali risultati sono tipicamente veri per tutte le funzioni naturali f ma non necessariamente per f costruite artificialmente . Per formularli con precisione è necessario avere una definizione precisa di una funzione naturale f per la quale il teorema è vero. Le funzioni costruibili nel tempo sono spesso utilizzate per fornire tale definizione.
Le funzioni costruibili nello spazio sono usate in modo simile, ad esempio nel teorema della gerarchia spaziale .
Questo articolo incorpora materiale da costruibile su PlanetMath , che è sotto licenza Creative Commons Attribution/Share-Alike License .
