L'APL è una lingua completa di Turing?

^{(elaborando il mio commento)}

In generale, la maggior parte dei linguaggi di programmazione e molte lingue specifiche del dominio sono Turing-complete . In pratica, è necessario progettare una lingua con molta attenzione per renderla non completa da Turing (quindi, quasi tutti i linguaggi di programmazione sono completati da Turing). Quando qualcuno ti dice: questo linguaggio Foo non è completo per Turing, devi essere molto sospettoso e richiedere una prova di ciò. Per la maggior parte dei linguaggi di programmazione, chiediti del problema di interruzione (se applicabile, quella lingua è Turing completo)

Cerca anche accidentale completezza di Turing , è divertente istruttivo.

APL è completo di Turing perché ha funzioni condizionali, ramificate e ricorsive. È anche completo di Turing perché potresti codificare in APL un interprete a macchina casuale .

Si noti che la completezza di Turing è un'astrazione teorica. In pratica, tutti i nostri computer digitali (e persino l'intera Internet) sono macchine a stati finiti; hanno una quantità limitata di memoria, ad es. 10 ¹⁴ bit per la maggior parte dei laptop nel 2015, quindi uno spazio di stato finito, ma enorme. Anche l'intero universo quantico può essere visto come una gigantesca macchina a stati finiti ( pan-computationism , Planck units , ...).

Tuttavia visualizzare la maggior parte dei computer (o linguaggi di programmazione) come macchine a stati finiti è inadeguato per la maggior parte degli scopi. Il modello Turing machine (o il suo equivalenti ) è spesso più adeguato. Scopri anche il teorema di Rice . Leggi anche il blog di J.Pitrat che ha alcuni viste interessanti.

Nota anche che complessità temporale & esplosione combinatoria & La complessità computazionale di solito conta molto più della completezza di Turing. Un programma che dà un risultato in miliardi di anni è inutile.