Si dice che un linguaggio di programmazione è la completezza di Turing se può simulare con successo una TM universale. Prendiamo ad esempio il linguaggio di programmazione funzionale.
Nella programmazione funzionale, la funzione ha la massima priorità su qualsiasi cosa. Puoi passare le funzioni in giro come qualsiasi primitivo o oggetto. Questa è chiamata funzione di prima classe.
Nella programmazione funzionale, la tua funzione non produce effetti collaterali, cioè le stringhe di output sullo schermo, cambiano lo stato delle variabili al di fuori del suo ambito. Ogni funzione ha una copia dei propri oggetti se gli oggetti vengono passati dall'esterno e gli oggetti copiati vengono restituiti quando la funzione termina il suo lavoro. Ogni funzione scritta puramente in stile funzionale è completamente indipendente da qualsiasi cosa al di fuori di esso. Pertanto, la complessità del sistema generale è ridotta. Questo è indicato come trasparenza referenziale.
Nella programmazione funzionale, ciascuna funzione può avere le sue variabili locali mantenute i suoi valori anche dopo che la funzione è stata chiusa. Questo è fatto dal garbage collector. Il valore può essere riutilizzato al prossimo richiamo della funzione. Questo è chiamato memoization.
Di solito una funzione dovrebbe risolvere solo una cosa. Dovrebbe modellare solo un algoritmo per rispondere a un problema. Pensi che una funzione in un linguaggio funzionale con le proprietà sopra descritte simuli una macchina di Turing?
- Funzioni (= algoritmi = Turing Machines) possono essere passati in giro come input e restituiti come output. TM accetta e simula anche altre TM
- Memoization modella l'insieme degli stati di una Turing Machine. Le variabili memorizzate possono essere utilizzate per determinare gli stati di una TM (ad esempio, quali linee eseguire, quale comportamento dovrebbe assumere in uno stato di offerta ...). Inoltre, è possibile utilizzare la memoizzazione per simulare la memoria interna del nastro. In un linguaggio come C / C ++, quando una funzione termina, perdi tutti i suoi dati interni (a meno che non lo memorizzi altrove al di fuori del suo ambito).
- Il set di simboli è l'insieme di tutte le stringhe in un linguaggio di programmazione, che è il livello più alto e la versione leggibile dall'uomo del codice macchina (opcode)
- Lo stato iniziale è l'inizio della funzione. Tuttavia, con la memoizzazione, lo stato di avvio può essere determinato mediante la memoizzazione o, se lo si desidera, l'istruzione switch / if-else nel linguaggio di programmazione imperativo. Ma poi, non puoi
- Stato di accettazione finale quando la funzione restituisce un valore o rifiuta se si verifica un'eccezione. Pertanto, la funzione (= algorithm = TM) è decidibile. Altrimenti, è indecidibile. Non sono sicuro di questo. Cosa pensi?
Il mio modo di pensare è vero su tutto questo?
Il motivo per cui porto funzionalità nella programmazione funzionale perché penso che sia più vicino all'idea di TM.
Quale esperienza con altri linguaggi di programmazione hai che ti fanno sentire l'idea della MT e le idee dell'Informatica in generale? Puoi specificare come pensi?