Bene nel mio libro si dice che "ci sono lingue non decidibili" e la prova è:
Every algorithm is a word. Then there are only countable algorithms. But there are uncountable languages and therefore more than algorithms
Perché si dice che ogni algoritmo è una parola? Una parola è una concatenazione di simboli, elementi di un alfabeto, quindi qual è la relazione tra una parola e un algoritmo? Qualcuno può spiegarmi questo?
Ecco un esempio solido.
Alcune lingue hanno sistemi di metaprogrammazione / pre-elaborazione che contengono codice che deve essere valutato in fase di compilazione. Questa può essere una semplice sostituzione, come le macro di C o più complesse.
Ci sono alcuni casi in cui il sistema di valutazione del codice di compilazione è abbastanza complesso da poter essere mostrato come completo da Turing. Il sistema Template di C ++ è l'esempio più infame di questo, sebbene anche Perl e Lisp abbiano questa proprietà.
Una proprietà famosa delle lingue complete di Turing è il problema di interruzione : è possibile costruire un programma valido in qualsiasi Linguaggio completo di Turing che finirà in un ciclo infinito e non terminerà. È anche possibile, in qualsiasi linguaggio completo di Turing, creare un programma valido per il quale non è possibile determinare se finirà o meno in un ciclo infinito .
Poiché il codice di preelaborazione deve essere valutato fino al completamento dal compilatore, ciò significa che in un linguaggio di programmazione con il completamento del processo di compilazione in tempo completo di Turing, è possibile costruire un programma sintatticamente corretto per il quale non è possibile compilatore per decidere cosa significa. Pertanto, C ++, Perl e Lisp sono lingue non decidibili nel caso generale. (Il che, ovviamente, non significa che non sia possibile scrivere programmi in essi. Solo che non tutti i programmi sintatticamente corretti scritti in essi possono essere compresi da un parser.)
Leggi altre domande sui tag algorithms turing-completeness