Intelligenza artificiale e macchina di Turing

Per capire tale affermazione bisogna almeno avere una idea generale di cosa sia una macchina di Turing: si tratta di un calcolatore idealizzato, nel senso che per concepirlo si prescinde dalla sua esistenza fisica, la quale potrebbe creare problemi di ordine limitativo. Ad essa non si impongono neanche limitazioni di calcolo o di durata dei processi di calcolo e si assume che la macchina funzioni sempre perfettamente. Le operazioni che essa è in grado di compiere sono estremamente elementari: è formata da caselle all’interno delle quali stanno informazioni e al contempo di una testina che ha il compito di leggere tali informazioni, stampare o cancellare informazioni già presenti sulla casella che osserva, a partire da una precisa configurazione interna. Le operazioni che essa può eseguire dipendono quindi dal fatto che tale testina si muove da sinistra a destra o viceversa, procedendo ad una casella per volta, cambiando quindi di volta in volta la propria configurazione interna.
È chiaro che una macchina così pensata, nonostante il suo carattere di illimitatezza riguardo alla durata dei processi, al numero delle operazioni, e di infallibilità implichi allo stesso tempo condizioni di finitezza (in ordine al numero di informazioni che può leggere, stampare, cancellare, all’alfabeto di simboli che utilizza) e di determinatezza (essa può compiere al più un’istruzione per ogni istante).