Funcție construibilă - Constructible function
În teoria complexității , o funcție construibilă în timp este o funcție f de la numere naturale la numere naturale cu proprietatea că f ( n ) poate fi construit din n de o mașină Turing în timpul ordinii f ( n ). Scopul unei astfel de definiții este de a exclude funcțiile care nu oferă o limită superioară în timpul rulării unei mașini Turing.
Definiții construibile în timp
Există două definiții diferite ale unei funcții construibile în timp. În prima definiție, o funcție f se numește construibilă în timp dacă există un întreg pozitiv n 0 și mașina Turing M care, având în vedere un șir 1 n format din n unele, se oprește după exact f ( n ) pași pentru toți n ≥ n 0 . În cea de-a doua definiție, o funcție f se numește construibilă în timp dacă există o mașină Turing M care, având un șir 1 n , generează reprezentarea binară a lui f ( n ) în timpul O ( f ( n )) (o reprezentare unară pot fi folosite în schimb, deoarece cele două pot fi interconvertite în timp O ( f ( n ))).
Există, de asemenea, o noțiune de funcție complet construibilă în timp. O funcție f se numește complet construibilă în timp dacă există o mașină Turing M care, dată fiind un șir 1 n format din n unele, se oprește după exact f ( n ) pași. Această definiție este puțin mai generală decât primele două, dar, pentru majoritatea aplicațiilor, oricare dintre definiții poate fi utilizată.
Definiții construibile în spațiu
În mod similar, o funcție f este construibilă în spațiu dacă există un număr întreg pozitiv n 0 și o mașină Turing M care, având în vedere un șir 1 n format din n unele, se oprește după utilizarea exact f ( n ) celule pentru toate n ≥ n 0 . În mod echivalent, o funcție f este construibilă în spațiu dacă există o mașină Turing M care, având în vedere un șir 1 n format din n unele, generează reprezentarea binară (sau unară) a lui f ( n ), în timp ce folosește doar O ( f ( n )) spațiu.
De asemenea, o funcție f este complet construibilă în spațiu dacă există o mașină Turing M care, având în vedere un șir 1 n format din n unele, se oprește după utilizarea exact f ( n ) celule.
Exemple
Toate funcțiile frecvent utilizate f ( n ) (cum ar fi n , n k , 2 n ) sunt construibile în timp și spațiu, atâta timp cât f ( n ) este cel puțin cn pentru o constantă c > 0. Nicio funcție care este o ( n ) poate fi construibilă în timp, cu excepția cazului în care este în cele din urmă constantă, deoarece nu este suficient timp pentru a citi întreaga intrare. Cu toate acestea, este o funcție construibilă în spațiu.
Aplicații
Funcțiile construibile în timp sunt utilizate în rezultatele teoriei complexității, cum ar fi teorema ierarhiei timpului . Sunt importante, deoarece teorema ierarhiei timpului se bazează pe mașinile Turing care trebuie să determine în timp O ( f ( n )) dacă un algoritm a făcut mai mult de f ( n ) pași. Acest lucru este, desigur, imposibil fără a putea calcula f ( n ) în acel timp. Astfel de rezultate sunt de obicei adevărate pentru toate funcțiile naturale f, dar nu neapărat adevărate pentru f construite artificial . Pentru a le formula cu precizie, este necesar să avem o definiție precisă pentru o funcție naturală f pentru care teorema este adevărată. Funcțiile construibile în timp sunt adesea folosite pentru a furniza o astfel de definiție.
Funcțiile construibile în spațiu sunt utilizate în mod similar, de exemplu în teorema ierarhiei spațiale .
Acest articol încorporează material din materialul construibil pe PlanetMath , care este licențiat sub licența Creative Commons Attribution / Share-Alike .
