In altre parole, è possibile creare un'espressione "regolare" PCRE che impiega Ackermann (m, m) per una stringa di lunghezza m?
In primo luogo, dobbiamo assumere una particolare implementazione PCRE per rendere il "tempo necessario" una funzione ben definita. Dobbiamo anche esigere che questa implementazione sia "sensata", ad esempio, non richiede deliberatamente molto più del necessario (per esempio, esattamente i passi di Ackermann (m, m)).
Quindi, nota che anche il backtracking più ingenuo richiede tempo esponenziale nella lunghezza della stringa. La funzione Ackermann cresce più velocemente di qualsiasi funzione esponenziale e le funzioni esponenziali sono ricorsive primitive.
Tuttavia, questo stabilisce solo che non esiste un'espressione regolare che prende il tempo di Ackermann (m, m). È concepibile che il tempo esatto preso da una particolare implementazione PCRE sia abbastanza strano da non essere ricorsivo primitivo anche se è limitato in alto da un esponenziale. Dopo tutto, le funzioni non hanno bisogno di crescere molto velocemente per essere ricorsive (primitive). Ad esempio, considera f (n) = il numero di programmi di arresto che possono essere scritti con n bit (che non è nemmeno ricorsivo, ma delimitato in precedenza di 2 ^ n).
Tuttavia, questa non è una domanda particolarmente interessante poiché
La domanda più sensata è se ci sia qualche funzione ricorsiva primitiva per ogni regex. Questo non è molto sensibile ai dettagli di codifica poiché di solito è facile tradurre da una codifica sensibile a un'altra. Quindi sospetto che la risposta sia sì, anche se non ho prove.
Leggi altre domande sui tag regular-expressions