# data[].attributes.body
Un automa può essere rappresentato mediante la funzione di transizione dello stato e di trasformazione delle uscite. Sebbene queste due funzioni siano sufficienti per descrivere un qualsiasi automa, potrebbero non essere di facile comprensione alle persone meno esperte

# data[].attributes.body
Un programma è un modello logico. Esso non è altro che il codice scritto il quale permette il funzionamento corretto dell'automa

# data[].attributes.body
È un modello matematico. La tabella associa a ogni stato e ad ogni ingresso, lo stato successivo e l'uscita dell'automa.

# data[].attributes.body
Un modello grafico che permette di visualizzare i collegamenti tra gli stati di un automa. Un diagramma degli stati è un modello grafico

# data[].attributes.attachment_link.title
Tinkercad | From mind to design in minutes

# data[].attributes.attachment_link.description
Tinkercad is a free, easy-to-use app for 3D design, electronics, and coding.

# data[].attributes.attachment_link.title
Tinkercad | From mind to design in minutes

# data[].attributes.attachment_link.description
Tinkercad is a free, easy-to-use app for 3D design, electronics, and coding.

# data[].attributes.body
Gli ASF permettono di risolvere un problema in modo efficiente e rapido. Le proprietà di un ASF sono descritte dal suo stato interno. Il numero di stati è un numero finito

# data[].attributes.body
Esso è una particolare macchina di Turing in cui la lunghezza del nastro è funzione lineare della dimensione dell'input

# data[].attributes.attachment_link.readable_text
Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dell'input. Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto (o di Tipo-1 secondo la gerarchia di Chomsky).

Come una macchina di Turing, il nastro di un LBA è composto da celle che possono contenere simboli appartenenti ad un alfabeto finito. L'automa possiede un numero finito di stati e la sua testina può leggere e scrivere una sola cella per volta.

L'unica restrizione posta nelle grammatiche di Tipo-1 è che le regole di produzione siano nella forma con .

Quindi nessuna derivazione di una stringa in linguaggio sensibile al contesto può contenere una forma sentenziale più lunga della stringa stessa. Dal momento che c'è una corrispondenza uno ad uno tra gli automi lineari limitati e queste grammatiche, non si necessita per il riconoscimento della stringa da parte dell'automa un nastro più lungo di quello occupato dalla stringa originale.

() linear bounded automaton, in Academic Press Dictionary of Science and Technology, Oxford, Elsevier Science & Technology, 1992.

# data[].attributes.attachment_link.description
Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dell'input. Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto (o di Tipo-1 secondo la gerarchia di Chomsky).

# data[].attributes.attachment_link.readable_text
Un esempio di macchina di Turing

In informatica, una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. In altre parole, si tratta di un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito su cui può leggere e/o scrivere dei simboli.

Introdotta nel 1936 da Alan Turing come modello di calcolo per dare risposta all'Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica, è un potente strumento teorico che viene largamente usato nella teoria della calcolabilità e nello studio della complessità degli algoritmi, in quanto è di notevole aiuto agli studiosi nel comprendere i limiti del calcolo meccanico; la sua importanza è tale che oggi, per definire in modo formalmente preciso la nozione di algoritmo, si tende a ricondurlo alle elaborazioni effettuabili con macchine di Turing.

La macchina di Turing ha la particolarità di essere retta da regole di natura molto semplice, ovvero di potersi descrivere come costituita da meccanismi elementari molto semplici; inoltre è possibile presentare a livello sintetico le sue evoluzioni mediante descrizioni meccaniche piuttosto intuitive. D'altra parte, essa ha la computabilità che si presume essere la massima: si dimostra, infatti, che essa sia in grado di effettuare tutte le elaborazioni effettuabili dagli altri modelli di calcolo noti all'uomo. Tra questi modelli di calcolo ricordiamo le funzioni ricorsive di Jacques Herbrand e Kurt Gödel, il lambda calcolo di Alonzo Church e Stephen Kleene, la logica combinatoria di Moses Schönfinkel e Haskell Curry, gli algoritmi di Markov, i sistemi di Thue, i sistemi di Post, le macchine di Hao Wang e le macchine a registri elementari o RAM astratte di Marvin Minsky. Di conseguenza si è consolidata la convinzione che per ogni problema calcolabile esista una MdT in grado di risolverlo: questa è la cosiddetta congettura di Church-Turing, la quale postula in sostanza che per ogni funzione calcolabile esista una macchina di Turing equivalente, ossia che l'insieme delle funzioni calcolabili coincida con quello delle funzioni ricorsive.

Gli algoritmi che possono essere implementati da una MdT si dicono "algoritmi Turing-computabili".

Nel 1936 venne pubblicato un articolo di Alan Mathison Turing intitolato On computable numbers, with an application to the Entscheidungsproblem, in cui l'autore risolveva negativamente l' Entscheidungsproblem (o problema della decidibilità), lanciato nel 1900 da David Hilbert e Wilhelm Ackermann.

La questione era stata posta da Hilbert nei seguenti termini: "esiste sempre, almeno in linea di principio, un metodo meccanico (cioè una maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso?"

I vantaggi derivanti dal possedere un tale metodo sono enormi e meritano tutta l'enfasi che Hilbert e molti altri al suo seguito diedero alla questione: un tale algoritmo sarebbe in grado di risolvere tutti i problemi matematici e, molto di più, sarebbe possibile ridurre ogni ragionamento umano a mero calcolo meccanizzabile. Una prima forte risposta la diede il matematico boemo Gödel in occasione della seconda conferenza sull' epistemologia delle scienze esatte di Königsberg (1930), in cui espresse per la prima volta pubblicamente le idee racchiuse nel suo più celebre lavoro sull'incompletezza dei sistemi formali coerenti ( primo teorema di incompletezza); Gödel dimostrò che la semplice coerenza di un sistema formale non può garantire che ciò che in esso viene dimostrato sia vero oppure falso. Il sogno di Hilbert stava già sfumando, quando Turing pubblicò il suo articolo, in cui dimostrò l'insolubilità dell'Entscheidungsproblem.

La soluzione proposta da Turing consiste nell'utilizzo di un modello matematico capace di simulare il processo di calcolo umano, scomponendolo nei suoi passi ultimi. La macchina è formata da una testina di lettura e scrittura con cui è in grado di leggere e scrivere su un nastro potenzialmente infinito, partizionato, in maniera discreta, in caselle. Ad ogni istante di tempo , la macchina si trova in uno stato interno ben determinato, risultato dell'elaborazione compiuta sui dati letti.

Lo stato interno, o configurazione, di un sistema è la condizione in cui si trovano le componenti della macchina ad un determinato istante di tempo . Le componenti da considerare sono:

il numero della cella osservata

il suo contenuto

l'istruzione da eseguire

Tra tutti i possibili stati, si distinguono:

una configurazione iniziale, per (prima dell'esecuzione del programma)

una configurazione finale, per (al termine dell'esecuzione del programma)

delle configurazioni intermedie, per (prima dell'esecuzione dell'istruzione )

Implementare un algoritmo in questo contesto significa effettuare una delle quattro operazioni elementari

spostarsi di una casella a destra

spostarsi di una casella a sinistra

scrivere un simbolo preso da un insieme di simboli a sua disposizione su una casella

cancellare un simbolo già scritto sulla casella che sta osservando

fermarsi

Eseguire un'operazione , tra gli istanti di tempo e , vuol dire passare dallo stato interno al . Più formalmente, questo si esprime in simboli come: da leggersi come: nello stato interno la macchina osserva il simbolo a₁, esegue l'operazione e si ritrova nello stato interno . Turing poté dimostrare che un tale strumento, dalle caratteristiche così rigidamente definite, è in grado di svolgere un qualsiasi calcolo, ma non si fermò qui; egli capì che la calcolabilità era in stretta relazione con la dimostrabilità e dunque, così come Gödel aveva distrutto i sogni di gloria dei Principia Mathematica di Russell e Whitehead, così le sue macchine potevano definitivamente chiudere la questione dell'Entscheidungsproblem.

Della MdT vengono considerate molteplici varianti ( models) che si dimostrano avere la stessa portata. Qui partiamo da una variante piuttosto semplice che possiamo chiamare macchina di Turing deterministica a un nastro e con istruzioni a cinque campi. Altre varianti sono presentate più avanti.

La macchina può agire sopra un nastro che si presenta come una sequenza di caselle nelle quali possono essere registrati simboli di un ben determinato alfabeto finito; essa è dotata di una testina di lettura e scrittura (I/O) con cui è in grado di effettuare operazioni di lettura e scrittura su una casella del nastro. La macchina si evolve nel tempo e ad ogni istante si può trovare in uno stato interno ben determinato facente parte di un insieme finito di stati. Inizialmente sul nastro viene posta una stringa che rappresenta i dati che caratterizzano il problema che viene sottoposto alla macchina. La macchina è dotata anche di un repertorio finito di istruzioni che determinano la sua evoluzione in conseguenza dei dati iniziali. L'evoluzione si sviluppa per passi successivi che corrispondono a una sequenza discreta di istanti successivi. Le proprietà precedenti sono comuni a molte macchine formali ( automa a stati finiti, automa a pila, ...). Caratteristica delle MdT è quella di disporre di un nastro potenzialmente infinito, cioè estendibile quanto si vuole qualora questo si renda necessario.

Ogni passo dell'evoluzione viene determinato dallo stato attuale nel quale la macchina si trova e dal carattere che la testina di I/O trova sulla casella del nastro su cui è posizionata e si concretizza nell'eventuale modifica del contenuto della casella, nell'eventuale spostamento della testina di una posizione verso destra o verso sinistra e nell'eventuale cambiamento dello stato. Quali azioni vengono effettuate a ogni passo viene determinato dall'istruzione, che supponiamo unica, che ha come prime due componenti e ; le altre tre componenti dell'istruzione forniscono nell'ordine il nuovo stato, il nuovo carattere e una richiesta di spostamento verso sinistra, nullo o verso destra.

Un'evoluzione della macchina consiste in una sequenza di sue possibili "configurazioni", ogni configurazione essendo costituita dallo stato interno attuale, dal contenuto del nastro (una stringa di lunghezza finita) e dalla posizione sul nastro della testina di I/O. Nei casi più semplici l'evoluzione ad un certo punto si arresta in quanto non si trova nessuna istruzione in grado di farla proseguire. Si può avere un arresto in una configurazione "utile" dal punto di vista del problema che si vuole risolvere; in tal caso quello che si trova registrato sul nastro all'atto dell'arresto rappresenta il risultato dell'elaborazione. Si può avere però anche un arresto "inutile" che va considerato come una conclusione erronea dell'elaborazione. Va subito detto che può anche accadere che un'evoluzione non abbia mai fine (Vedi la successiva sezione e Problema della fermata).

Si definisce macchina di Turing deterministica a un nastro e istruzioni a cinque campi, termine che abbreviamo con MdT1n5i, una macchina formale della seguente forma:

è un insieme finito detto insieme degli stati della macchina;

è un elemento di detto stato iniziale della ;

è un sottoinsieme di detto insieme degli stati finali della ;

è un alfabeto finito detto alfabeto del nastro della

è un carattere dell'alfabeto detto segno di casella vuota del nastro della

è detta funzione di transizione della macchina.

Se , la corrispondente quintupla può considerarsi come l'istruzione che viene eseguita quando la macchina si trova nello stato e la testina di I/O legge sulla casella sulla quale è posizionata; essa comporta la transizione allo stato , la scrittura del carattere e:

quando lo spostamento della testina di una posizione a sinistra,

quando nessuno spostamento della testina,

quando lo spostamento della testina di una posizione a destra.

L'importanza della MdT deriva dal fatto che permette di compiere tutte le elaborazioni effettuate mediante le macchine (elettroniche o meccaniche) apparse nella storia dell'umanità, incluse le elaborazioni che oggi si eseguono con le tecnologie più avanzate e gli odierni computer, e perfino le dimostrazioni matematiche che l'umanità ha raccolto nel corso della sua storia.

Infatti, tutte le macchine che si conoscono possono essere ricondotte al modello estremamente semplice di Turing. Ad esempio, anche i più complessi computer odierni possono essere ricondotti a questo modello:

Innanzitutto, si individuano macchine relativamente semplici che effettuino le operazioni aritmetiche di base, e schemi di composizione di queste macchine che permettono di calcolare tutte le funzioni che hanno in ingresso numeri naturali. Queste funzioni corrispondono alle espressioni ottenute combinando come si vuole le suddette operazioni.

Quindi, si individuano versioni della MdT più ricche di risorse, che consentano di descrivere più agevolmente operazioni via via più complesse e che riguardino entità discrete dei generi più vari (numeri razionali, grafi, stringhe, espressioni simboliche di varia natura, ...), ma tutte riconducibili a numeri naturali; le elaborazioni e le entità dei tipi più vari devono essere prese in considerazione per sostenere la congettura di Church-Turing.

Proseguendo in questa direzione, si introducono MdT dotate di memorie complesse, come sequenze di nastri e memorie bidimensionali e tridimensionali, assimilabili ai dischi e alle pile di dischi; macchine che sono dotate della capacità di organizzare le istruzioni in un modo assimilabile al richiamo di un sottoprogramma come richiesto dai linguaggi di programmazione in uso.

Ulteriori arricchimenti possono includere calcoli simbolici ed elaborazioni parallele.

A questo punto si deve anche aggiungere che della MdT risulta opportuno anche considerare varianti non deterministiche, macchine formali che sono in grado di portare avanti contemporaneamente diverse elaborazioni, in numero illimitato. Queste macchine formali, a prima vista lontane da modelli di meccanismi concretamente realizzabili, possono considerarsi idealizzazioni di sistemi di computer che operano in parallelo, sistemi che la odierna tecnologia consente di realizzare abbastanza comunemente (i cosiddetti cluster).

Con questo ragionamento si ottengono macchine formali che, in linea di principio, si possono ricondurre alla MdT introdotta inizialmente, ma che possono essere programmate molto più agevolmente, e soprattutto che possono essere realizzate con le tecnologie disponibili oggi. Dimostrare che una di queste macchine può risolvere un certo problema vuol dire dimostrare che anche la MdT può risolverlo. La conclusione è che tutte le computazioni effettuabili dalle macchine a noi note sono effettuabili anche dalla MdT.

Una macchina che permetta di risolvere tutti i problemi risolvibili anche dalla MdT si dice "Turing-equivalente". La conclusione è che tutte le computazioni effettuabili dalla MdT sono effettuabili anche da tutte le macchine di cui si è in grado di dimostrare l'equivalenza con la MdT.

Quindi, l'importanza della MdT è duplice: non solo è il modello teorico di macchina più "potente" che si conosca, ma può essere usato anche per verificare la potenza di nuovi modelli teorici. È possibile dimostrare l'equivalenza con la MdT anche servendosi di un modello più semplice e che si sa già essere Turing-equivalente. Ciò permette di riutilizzare facilmente, per un certo modello di macchina, i risultati teorici ottenuti per altri modelli di macchina.
Inoltre, la MdT e gli altri modelli possono essere usati per dimostrare le capacità computazionali dei linguaggi di programmazione (in quanto vengono dimostrate le capacità delle rispettive macchine astratte).

Tutte queste considerazioni rendono ragionevole sostenere la congettura di Church-Turing. Tuttavia, esse riguardano la calcolabilità degli algoritmi, e non la loro trattabilità: macchine equivalenti sono realizzate in modo diverso, e quindi possono eseguire la stessa computazione con un diverso numero di passi o dispendio di risorse (memoria, tempo, e altre). Ad esempio, un calcolo che un odierno computer esegue in pochi secondi richiederebbe un numero enorme di passi se eseguito su un meccanismo dotato di dispositivi operativi estremamente semplici come quelli della MdT. In sintesi, macchine diverse possono risolvere gli stessi problemi con programmi che hanno una diversa complessità computazionale.

Il problema dell'arresto e la sua indecidibilità

In talune circostanze può essere utile considerare una MdT che presenta un'evoluzione illimitata (infatti si considerano infinite le risorse di spazio e tempo a disposizione della macchina). Ad esempio interessa far procedere "illimitatamente" (cioè "quanto risulta utile") una MdT che genera gli elementi di una successione di oggetti (ad es. i successivi numeri primi, o i successivi numeri di Mersenne, o le successive cifre decimali di un numero irrazionale come pi greco). In altri casi invece un'evoluzione illimitata di una MdT è considerata un insuccesso. Quando si vuole che una MdT ricerchi in un insieme numerabile un elemento con determinate caratteristiche ed essa procede nella ricerca senza fornire alcuna indicazione, ci si trova in una situazione decisamente insoddisfacente: non si sa se interrompere un'elaborazione inutile oppure attendere ancora un risultato che potrebbe essere fornito dopo un ulteriore lavoro in tempi accettabili.

È dunque importante poter stabilire se una MdT, o un altro sistema formale equivalente ("lambda-calcolo" di Church, ad es.), quando le si sottopone una stringa (di dati) si arresti o meno. Questo è detto problema della fermata o problema dell'arresto della macchina di Turing. Si trovano casi nei quali si dimostra o si verifica che si ha l'arresto, casi per i quali si dimostra che l'evoluzione non si arresta ma potrebbe procedere all'infinito e casi per i quali non si sa dare risposta.

Sembra ragionevole cercare un procedimento generale per decidere uno di questi problemi. Dato che le MdT si rivelano in grado di risolvere tutti i problemi che si sanno risolvere con gli altri procedimenti noti, è sensato chiedersi se esiste una macchina di Turing in grado di decidere per una qualsiasi coppia (M, d) costituita da una MdT M e da una stringa di dati d se, quando si fornisce d a M, questa si evolve fino ad arrestarsi o meno. Questa richiesta è resa ancor più significativa dall'esistenza, dimostrata dallo stesso Turing, di una cosiddetta macchina di Turing universale, macchina in grado di simulare qualsiasi evoluzione di qualsiasi MdT (anche le evoluzioni di se stessa!). Ebbene Turing ha dimostrato che la macchina di Turing universale non è in grado di decidere in ogni caso il problema dell'arresto. Quindi nessuna macchina di Turing può farlo. Questo risultato negativo si esprime dicendo che il problema dell'arresto è Turing-indecidibile. Se si accetta la congettura di Church-Turing sulla portata della macchina di Turing, si conclude che il problema dell'arresto della macchina di Turing è indecidibile.

Questo risultato negativo costituisce un limite per tutti i meccanismi computazionali; esso costituisce un risultato limitativo di grande importanza generale e per lo studio degli algoritmi. L'importanza generale dipende dal fatto che ogni procedimento dimostrativo automatico si trova equivalente a una computazione che può effettuarsi con una macchina di Turing. Va posto in rilievo che la Turing-indecidibilità del problema dell'arresto si dimostra equivalente al teorema di incompletezza di Gödel, il primo fondamentale risultato limitativo per la matematica. Si trova inoltre nello studio degli algoritmi e della loro complessità che dalla indecidibilità dell'arresto si deducono abbastanza agevolmente molti altri risultati limitativi.

Modello di una parte dell'Analytical Engine di Babbage in mostra al Museo della scienza di Londra[4].

La nozione di "macchina computazionale" ha un'origine precedente ai lavori di Turing, Robin Gandy (1919-1995) - studente di Alan Turing (1912-1954) e successivamente amico per tutta la vita - ne tracciò la discendenza a partire da Charles Babbage (1834).

Ecco come descrive la " Teoria di Babbage": That the whole of development and operations of analysis are now capable of being executed by machinery. (Così l'intero modo di sviluppare e di fare operazioni di analisi può essere eseguito da una macchina.)

L'analisi di Gandy della macchina analitica di Babbage ricava le seguenti operazioni:

1. The arithmetic functions +, −, ×, where − indicates "proper" subtraction: x − y = 0 if y ≥ x.

2. Any sequence of operations is an operation.

3. Iteration of an operation (repeating n times an operation P).

4. Conditional iteration (repeating n times an operation P conditional on the "success" of test T).

5. Conditional transfer (i.e. conditional "goto").

ossia

1. Le funzioni aritmetiche +, −, ×, dove − indica la sottrazione "in senso proprio": x − y = 0 se y ≥ x.

2. Una qualunque sequenza di operazioni è un'operazione.

3. L'iterazione di un'operazione (ripetere un'operazione P un certo numero di volte).

4. L'iterazione condizionata (ripetere più volte un'operazione P condizionata dal "successo" del test T).

5. Il trasferimento condizionato (i.e. "goto" condizionato).

Gandy sostiene che "le funzioni che possono essere calcolate da (1), (2) e (4) sono precisamente quelle calcolate da Turing.".

Cita inoltre altre "macchine di calcolo universale", incluse quelle di Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937).

Costante fondamentale è programmare un numero fisso di sequenze di operazioni aritmetiche (anche se le importanti caratteristiche di interazione condizionata e trasferimento condizionato per la teoria di calcolo di una macchina non sono universalmente riconosciute).

Il problema della decisione (Entscheidungsproblem): la decima questione di Hilbert

Nonostante il valore delle questioni poste dal famoso matematico David Hilbert nel 1900 sia innegabile, bisogna considerare che un aspetto del decimo dei problemi che pose andò alla deriva per almeno trent'anni senza essere impostato in maniera precisa.

Segue la formulazione originale di Hilbert per il decimo problema:

10. Determination of the solvability of a Diophantine equation. Given a Diophantine equation with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability... The Entscheidungsproblem must be considered the main problem of mathematical logic.(10. Determinazione della risolvibilità di un'equazione diofantea. Data un'equazione diofantea in qualsiasi numero d'incognite e a coefficienti interi razionali: ideare un procedimento per mezzo del quale si possa stabilire, in un numero finito di operazioni, se l'equazione sia risolubile negli interi razionali. L'Entscheidungsproblem (problema della decisione per la logica del primo ordine) è risolto quando si arriva ad una procedura che permette di decidere attraverso un numero finito di espressioni la validità o soddisfabilità per qualunque espressione logica fornita. (...) L'Entscheidungsproblem dev'essere considerato il problema principale della logica matematica (...)).

Già nel 1922 questa nozione di Entscheidungsproblem venne sviluppata da Heinrich Behmann:

(...) most general form of the Entscheidungsproblem [is] as follows: A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion... Behmann remarks that... the general problem is equivalent to the problem of deciding which mathematical propositions are true. If one were able to solve the Entscheidungsproblem then one would have a "procedure for solving many (or even all) mathematical problems".

((...) segue la formula più generale dell'Entscheidungsproblem: È richiesta una prescrizione abbastanza definita, generalmente applicabile, tale da consentirci di decidere in un numero finito di passaggi verità o falsità di una data asserzione puramente logica. Behmann osserva: (...) il problema generale coincide con il problema di decidere quali proposizioni matematiche sono vere. (...) Se qualcuno fosse in grado di risolvere l'Entscheidungsproblem, allora avrebbe una "procedura per risolvere la maggior parte (o addirittura tutti) i problemi matematici").

Nel 1928 presso il congresso internazionale dei matematici, Hilbert stesso "formulò la sua questione in modo abbastanza preciso. Primo, se la matematica sia completa, (...) secondo se sia consistente, (...) terzo se sia decidibile" (Hodges). Alle prime due domande rispose Kurt Gödel nel 1930 (nello stesso convegno in cui Hilbert pronunciò il suo discorso di commiato); il terzo - l'Entscheidungsproblem - dovette aspettare fino alla metà degli anni '30. Il problema stava nel fatto che una risposta richiedeva una definizione precisa di " prescrizione definita generalmente applicabile", o, come verrà chiamata dal professor Alonzo Church di Princeton, "calcolabilità effettiva", e nel 1928 non ne esisteva alcuna.

Tuttavia negli anni successivi Emil Post sviluppò una definizione per "un lavoratore in grado di spostarsi tra postazioni differenti, scrivendo e cancellando segni secondo una lista di istruzioni" (1936), ed analogamente fecero Church e alcuni suoi allievi ( Stephen Kleene e J. B. Rosser) con il lambda calcolo e la teoria di Gödel sulle funzioni ricorsive primitive (1934). La relazione di Church (pubblicata nell'aprile del 1936) risolveva l'Entscheidungsproblem mostrandone l'indecidibilità, battendo sul tempo Turing (la cui teoria venne formulata nel maggio del 1936 ma pubblicata solo nel 1937). (Nel frattempo anche Post lavorò sul tema, collocandosi però nell'autunno del 1936, quindi successivamente a Turing). Il lavoro di Turing tuttavia si discosta nettamente dai lavori di Church e di Post, essendo caratterizzato dalla costruzione diretta di un'argomentazione che partiva dai principi fondativi della questione (Hodges).

Nella primavera del 1935 Turing, da giovane studente presso il King's College di Cambridge, accettò la sfida. Era stato stimolato dalle lezioni del logico Max Newman che lo introdusse al lavoro di Gödel e all'Entscheidungsproblem (problema della fermata), le ultime frontiere della conoscenza matematica. Newman impostò la questione sul concetto di "processo meccanico" come mezzo per analizzare il problema di Hilbert, una scelta fortemente criticata dalla comunità matematica inglese. Nel necrologio di Turing del 1955 Newman scrive:

Gandy scrive:

Il precoce interesse di Turing sulla macchina venne stimolato dalla macchina per scrivere della madre.

L'idea principale di Turing fu che l'Entscheidungsproblem di Hilbert potesse essere risolto attraverso un processo meccanico da una macchina (che successivamente venne teorizzata come la TM) e anche se gli giunse come illuminazione giovanile di una grande mente, in realtà aveva radici più profonde. Turing infatti per tutta la vita aveva dimostrato interesse nelle macchine, a partire dalle riflessioni infantili sulla macchina da scrivere della madre, che cercavano di estrapolarne le caratteristiche, che la determinavano appunto come macchina.

La sua tesi di dottorato, intitolata " Systems of Logic Based on Ordinals", contiene la seguente definizione di una "funzione calcolabile":

Quando Turing tornò in Inghilterra, dopo un periodo di formazione presso il college di Princeton, venne impiegato in ambito bellico dal governo inglese per infrangere i codici segreti tedeschi creati dalla macchina crittografica Enigma.

Venne poi coinvolto nella progettazione dell' ACE (Automatic Computing Engine): "la proposta ACE [di Turing] era effettivamente autonoma e le sue radici non risiedevano nell'EDVAC [l'iniziativa degli Stati Uniti], ma nella sua stessa macchina universale" (Hodges). Continuando così a sviluppare gli argomenti sull'origine e la natura di ciò che è stato nominato da Kleene (1952) la "tesi di Turing".

Ma ciò che Turing dimostrò con il suo modello di macchina computazionale apparve in forma definitiva solo nel suo articolo " On Computable Numbers, with a Application to the Entscheidungsproblem" (1937). In questo scritto infatti, per la prima volta concettualizza quella che diventerà la macchina di Turing:

1937-1970: Il "computer digitale", la nascita dell'"informatica"

Nel 1937 a Princeton, mentre stava lavorando alla sua tesi di dottorato, Turing costruì dal principio un moltiplicatore elettrico, realizzando i propri trasmettitori elettromeccanici. "Il compito di Alan era quello di incarnare la progettazione logica di una macchina Turing in una rete di trasmettitori azionati a interruttori...". Mentre Turing all'inizio sembrava essere solamente curioso, altri stavano andando nella stessa direzione sia in Germania ( Konrad Zuse, 1938), che negli Stati Uniti ( Howard Aiken e George Stibitz, 1937); i frutti delle loro fatiche furono usati dai militari dell'Asse e degli Alleati nella seconda guerra mondiale.

Nella prima metà degli anni '50 Hao Wang e Marvin Minsky ridussero la macchina Turing a una forma più semplice (un precursore della macchina sviluppata poi da Martin Davis); contemporaneamente anche i ricercatori europei stavano riducendo il nuovo computer elettronico a un oggetto teorico simile a quello che veniva chiamata "macchina di Turing".

Alla fine degli anni '50 e all'inizio degli anni '60, gli sviluppi paralleli e coincidenti di Melzak e Lambek (1961), Minsky (1961) e Shepherdson e Sturgis (1961) portarono avanti il lavoro europeo e ridussero la macchina di Turing a un computer più intuitivo, simile ad un modello astratto chiamato "contatore macchina"; Elgot e Robinson (1964), Hartmanis (1971), Cook e Reckhow (1973) svilupparono ancora il progetto con la "macchina a registro" e i modelli di "macchina ad accesso casuale" - ma fondamentalmente tutti sono "macchine di Turing multi-nastro" con aggiunti set di istruzioni aritmetiche.

Oggi, le macchine per il calcolo, la registrazione e l'accesso casuale e la loro procreatrice macchina di Turing, continuano ad essere i modelli di scelta per i teorici che studiano questioni riguardanti la teoria della computazione. In particolare fa uso della macchina di Turing la teoria della complessità computazionale.

In base agli oggetti da manipolare nella computazione (numeri interi non-negativi o stringhe alfa-numeriche), due modelli hanno ottenuto una posizione dominante nella teoria basata sulle macchine complessa: la TM multinastro off-line e la RAM ( random access machine) di Cook e Reckhow anche se quest'ultima assume un ruolo principale solamente nelle aree relative all'analisi degli algoritmi.

In questo paragrafo le maggiori varianti della MdT definita in precedenza vengono presentate in termini discorsivi, lasciando ad articoli specifici le considerazioni più precise e complete.

La MdT con più nastri differisce dalla classica sostanzialmente per il tipo della funzione di transizione; questa nel caso dei 3 nastri ha la forma

.

Questa funzione si fa dipendere dalla transizione da quanto viene letto sulle caselle su cui si trovano le testine relative ai diversi nastri e stabilisce quali caratteri devono essere modificati sui vari nastri e come si devono eventualmente spostare le testine.

È abbastanza evidente come questa macchina sia più semplice da usare della classica. Ad es. con essa si possono agevolmente copiare stringhe da un nastro all'altro e con porzioni di nastro si possono rendere disponibili sequenze di memorie indirizzabili abbastanza agevolmente. Con una macchina a tre nastri si può implementare molto facilmente un'operazione aritmetica come la somma di due numeri espressi mediante cifre decimali. Similmente e con gli opportuni accorgimenti e con l'uso di altri opportuni registri, lo si può intuire, si riescono a implementare altre operazioni aritmetiche o su entità discrete.

Per dimostrare che una macchina a più nastri P ha la stessa portata di quelle ad un solo nastro si tratta di individuare una di queste, denotiamola M che consente di simularne le evoluzioni. Questa simulazione viene effettuata simulando su un solo nastro della M i molti nastri della P. Si possono avere configurazioni della M che simulano configurazioni della P utilizzando scritture particolari che separano le aree nelle quali sono riprodotti i diversi nastri della P e segnalano le posizioni sulle quali si trovano le varie testine di I/O. A ciascun passo della P si fa corrispondere una serie di passi della M con i quali si sistemano i vari nastri e le posizioni delle relative testine. Si può capire come con un gran numero di spostamenti e di cambiamenti di stato si possono simulare le mosse della P.

Consente di simulare abbastanza facilmente macchine a più nastri e di effettuare elaborazioni grafiche. Ulteriori varianti possono servirsi di memorie tridimensionali e simili.

La macchina di Turing non deterministica si distingue da quella deterministica definita in precedenza per il fatto che, in presenza di un determinato stato e di un determinato carattere letto, essa permette più transizioni.

Una macchina di Turing non deterministica , con grado di non determinismo , è così definita:

dove le sole differenze rispetto alla definizione iniziale riguardano la presenza dell'intero e il genere della funzione di transizione:

Le sue configurazioni consistono quindi di insiemi finiti di configurazioni deterministiche, la cui cardinalità potrebbe crescere illimitatamente con il procedere di un'evoluzione.

Le computazioni che essa è in grado di svolgere sono descrivibili come insiemi di computazioni sviluppati da repliche della MdT deterministica, repliche che potrebbero rendersi necessarie ad ogni passo dell'evoluzione. Si osserva che questa richiesta oggi non dovrebbe affatto stupire, in quanto realizzabile con le tecniche dei computer collegati in rete ed effettivamente realizzata nella prassi delle elaborazioni distribuite.

Dato che ogni macchina deterministica si può considerare una particolare macchina non deterministica, si tratta di dimostrare che con una macchina deterministica M si riesce a simulare il comportamento di una macchina non deterministica N. Più precisamente supponiamo che N sia una macchina ad un nastro e che la M sia una macchina che dispone di una memoria bidimensionale, memoria assimilabile alla disponibilità di più nastri il cui numero sia aumentabile. La macchina M riesce a simulare con ciascuno dei suoi stati gli stati multipli della macchina N e con i suoi molti nastri i singoli nastri replicati della N. Ad ogni passo della N la M fa corrispondere una serie di passi con i quali fa evolvere i diversi nastri che rappresenta nella sua memoria bidimensionale e, in corrispondenza a una transizione non deterministica di molteplicità k, replica il nastro interessato trasformandolo nei k nastri richiesti.

In questo modo si vede come la macchina M possa simulare la N. Si osserva che alcuni singoli passi della macchina non deterministica richiedono un gran numero di passi e di appositi stati della deterministica.

Equivalenza tra MdT a k nastri e MdT ad un nastro

La capacità computazionale di una MdT non dipende dal numero di nastri che essa utilizza; questo è possibile dimostrarlo attraverso la simulazione. Indichiamo con T k la macchina di Turing a k nastri e con T quella ad un nastro. Scriviamo l'input della macchina T k sulla macchina T ovviamente un simbolo per ogni cella, quando la macchina T leggerà il primo simbolo essa per eseguire una quintupla della macchina T k avrà bisogno di leggere k caratteri ricordando ogni volta il k-esimo carattere letto; verificato che la quintupla può essere eseguita a questo punto riporterà indietro la testina di k celle e può procedere all'esecuzione della quintupla sovrascrivendo i k caratteri; a questo punto la testina si troverà sulla cella contenente l'ultimo carattere scritto. Gli ultimi passaggi da eseguire sono il cambio di stato interno e il movimento della testina. È facile notare come l'insieme degli stati di T ha cardinalità maggiore rispetto all'insieme degli stati di T k.

Le macchine di Turing possono essere ulteriormente semplificate, senza perdita di portata computazionale. Le semplificazioni possibili sono (non attuabili contemporaneamente):

1. nastro illimitato solo in una direzione;

2. alfabeto di soli due caratteri, uno dei quali il simbolo blank;

3. solo due stati.

La dimostrazione dell'equivalenza con la macchina definita inizialmente con quelle con le caratteristiche 2 e 3 costituiscono il primo teorema di Shannon.

Un ulteriore modello semplificato di MdT è quello di avere tre MdT che compiono operazioni elementari (scrittura del carattere 1, scrittura del simbolo blank, spostamento della testina a destra, spostamento a sinistra, nessuna operazione) e ottenere da queste una nuova MdT tramite composizione per diramazione.

La Macchina di Turing universale è quella che calcola la funzione u, che a sua volta è in grado di simulare il comportamento di qualunque macchina di Turing. La funzione u prende in input una codifica della macchina M che si voglia eseguire (ovvero un numero che una volta decodificato fornisca il codice di M) e una codifica dei parametri iniziali ad M.

La macchina di Turing, nonostante sia una "macchina astrattamente definita", è un ottimo modello per descrivere le macchine reali. In seguito alcune argomentazioni:

1. Tutto ciò che un computer reale può computare, lo può fare anche una MdT. Per esempio: "Una macchina di Turing può simulare ogni tipo di subroutine trovato nei linguaggi di programmazione, incluse procedure ricorsive e ognuno dei parametri di passaggio del meccanismo conosciuti" (Hopcroft and Ullman). Anche un automa a stati finiti (FSA) sufficientemente capiente può imitare ogni computer reale, trascurando l'IO. Perciò, uno statuto sulle limitazioni della macchina di Turing sarebbe applicato anche ai computer reali.

2. La differenza sta solo nella capacità di una MdT di manipolare una quantità illimitata di dati. Comunque, dato un tempo finito, una MdT (come una macchina reale) può processare una quantità finita di dati.

3. Come una MdT, una macchina reale può allargare il suo spazio di archiviazione secondo necessità, acquisendo dischi aggiuntivi o altri sistemi di archiviazione.

4. Le descrizioni di programmi per macchine reali, usando semplici modelli astratti, sono spesso molto più complesse di descrizioni ottenute usando la macchina di Turing. Per esempio, una MdT può assumere poche centinaia di stadi descrivendo un algoritmo, mentre un automa a stati finiti deterministico (DFA) equivalente ne fornirebbe quadrillioni partendo da una macchina reale data. Questo rende le rappresentazioni del DFA impossibili da analizzare.

5. Le macchine di Turing descrivono algoritmi indipendentemente da quanta memoria utilizzano. Ogni macchina corrente possiede dei limiti di memoria contenuta, ma questi limiti possono essere ampliati nel tempo arbitrariamente. Le macchine di Turing ci permettono di produrre enunciati sugli algoritmi che (teoricamente) avranno valore eterno, indipendentemente da evoluzioni nell'architettura convenzionale della meccanica dei computer.

6. Le MdT semplificano i postulati degli algoritmi. Infatti algoritmi che girano su una macchina Turing-equivalente astratta sono generalmente più astratti delle loro controparti su macchine reali, perché hanno una precisione arbitraria delle tipologie di dati possibili e non devono mai tener conto di condizioni impreviste (inclusi, ma non solo, casi di memoria limitata).

A. Hodges, Alan Turing. Storia di un Enigma, Torino, Bollati Boringhieri, 1991 [1983].

J. Hopcroft, J. Ullman (1979), Introduction to Automata Theory, Languages and Computation, Addison-Wesley ISBN 0-201-02988-X
Versione italiana: J. Hopcroft, R. Motwani, J. Ullman, Automi, linguaggi e calcolabilità, Pearson, 2003, ISBN 978-88-7192-552-3

Douglas Hofstadter (1979), Gödel, Escher, Bach: an Eternal Golden Braid
Versione italiana: Godel, Escher, Bach: un'eterna ghirlanda brillante, Adelphi, Milano, 1990, ISBN 88-459-0755-4

Arto Salomaa, Computation and automata, Cambridge University Press, 1985, ISBN 0-521-30245-5

Ivor Grattan-Guiness, The search for Mathematical Roots, 1870-1940, Princeton University Press, 2000, ISBN 0-691-05858-X

(EN) Jackson, Philip C., Introduction to artificial intelligence , 1985.

Arbib, Michael A., La mente, le macchine e la matematica.

Davis, Martin, Il calcolatore universale, Milano, Adelphi, 2003, ISBN 9788845917929.

Cappuccio, Massimiliano, Alan Turing: L'uomo, La macchina, L'enigma, Milano, AlboVerso, 2005, ISBN 88-89130-29-6.

Stillwell, John, Da Pitagora a Turing, Bologna, ETS, 2018, ISBN 978-884675042-6.

Martin Davis, The Undecidable, Dover Pubns; Dover edizione, 2004, ISBN 0486432289.

Robin Gandy, The Confluence of Ideas in 1936, 1988.

Alan Turing (1936): On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc., 42 pp. 230-265 Accessibile anche in linea

Macchine equivalenti alla MdT

Mauro Cappelli, macchina di Turing , in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.

Macchina di Turing , in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

(EN) Turing machine , su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

(EN) Eric W. Weisstein, Macchina di Turing , su MathWorld, Wolfram Research.

(EN) Macchina di Turing, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL

(EN) Turing Machine nella Stanford Encyclopedia of Philosophy

Andrea de Prisco, (Algoritmi e Macchine di Turing (JPG), in MCmicrocomputer, n. 59, Roma, Technimedia, gennaio 1988, p. 120, ISSN 1123-2714WC · ACNP).

Articolo divulgativo , su startmag.it.

# data[].attributes.attachment_link.description
In informatica, una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite.

# data[].attributes.attachment_link.readable_text
Un automa a pila o Push Down Automa (PDA) è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila, una struttura dati i cui dati possono essere estratti in ordine necessariamente inverso rispetto a quello di inserimento. Un automa a pila è in grado di riconoscere ed accettare tutti i linguaggi che nella teoria delle grammatiche formali sono detti non contestuali, ovvero di tipo 2 secondo la classificazione gerarchica di Chomsky.

L'automa a pila non deterministico è un sistema formale composto da [1], dove:

1. è l'alfabeto di input;

2. è l'alfabeto dei simboli della pila;

3. è il carattere iniziale della pila;

4. è un insieme finito e non vuoto di stati;

5. è lo stato iniziale;

6. è l'insieme degli stati finali;

7. è la funzione parziale di transizione ( è la stringa vuota).

Un automa a pila deterministico è un automa a pila tale che per ogni carattere a di , per ogni stato di e per ogni stato di si ha

Dato un automa a pila si dice configurazione di una tripla , dove appartiene a , a e a .

Un automa a pila ha due diversi modi di accettare un linguaggio:

Dato un automa a pila , una sua configurazione è di accettazione se . In base a tale definizione una stringa è accettata da un automa a pila se e solo se al termine dell'elaborazione di la pila è vuota.

Esempio

Vediamo ora l'esempio di un automa a pila deterministico che riconosca il linguaggio per stato finale:

, con

alfabeto di input:

alfabeto dei simboli della pila:

carattere iniziale della pila:

stati:

stato iniziale:

stati finali:

funzione di transizione ( è la stringa vuota) - costituita dalle seguenti 6 istruzioni:

,

,

,

,

,

.

Le prime due istruzioni dicono che in uno stato p, per ogni 0 letto viene aggiungo A sulla pila. Aggiungere un A su un altro A è formalizzato dalla scritta AA (così come AZ simbolizza immettere un A su una Z). La terza e quarta istruzione indicano una epsilon-transizione (ossia una transizione non deterministica, che può avvenire in qualsiasi momento) dallo stato p allo stato q. La quinta istruzione dice che in uno stato q, per ogni 1 letto, viene tirato via un A dalla cima della pila. Infine, la sesta istruzione dice che la macchina passa dallo stato q allo stato finale r solamente quando la pila è costituita dalla sola variabile Z (ossia la variabile inizilamente sulla pila). Questo vuol dire che l'automa accetta unicamente la parole dove il numero di 0 sono bilanciate con il numero dei successivi 1.

Dato un automa a pila , una sua configurazione è di accettazione se e appartiene a . Secondo questa definizione una stringa è accettata da se e solo se al termine dell'elaborazione di stringa l'automa si trova in uno stato finale.

In generale, dato un automa a pila , il linguaggio riconosciuto da per pila vuota è diverso dal linguaggio riconosciuto da per stato finale. È importante notare, tuttavia, che la classe dei linguaggi riconosciuti dagli automi a pila non cambia sia che si scelga l'accettazione per pila vuota che per stato finale. Vale, cioè che è un linguaggio accettato per pila vuota da un automa a pila se e solo se è un linguaggio accettato per stato finale da un automa a pila . In particolare, la classe dei linguaggi accettati dagli automi a pila coincide con quella dei linguaggi liberi da contesto.

# data[].attributes.attachment_link.description
Un automa a pila o Push Down Automa (PDA) è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila, una struttura dati i cui dati possono essere estratti in ordine necessariamente inverso rispetto a quello di inserimento.

# data[].attributes.attachment_link.readable_text
Un automa a stati finiti ( ASF o FSA, dall' inglese finite state automaton, al plurale: f. s. automata) o macchina a stati finiti ( FSM, dall'inglese finite state machine) è un tipo di automa che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi. Grazie alla sua semplicità e chiarezza questo modello è molto diffuso nell' ingegneria e nelle scienze, soprattutto nel campo dell' informatica e della ricerca operativa.

Un automa a stati finiti può essere utilizzato sia per modellare un sistema esistente che per modellare un nuovo sistema formale in grado di risolvere alcuni problemi esistenti. A quest'ultima categoria appartengono i cosiddetti riconoscitori di linguaggi e i traduttori. L'usuale rappresentazione grafica di un automa a stati finiti è il grafo orientato.

Nello specifico, con gli automi a stati finiti, si possono modellare tutti i sistemi che possiedono le seguenti caratteristiche:

Dinamicità: caratteristica di evolvere nel tempo passando da uno stato ad un altro.

Discretezza: caratteristica che indica che le variabili d'ingresso e gli stati del sistema da modellare possono essere espressi con valori discreti.

Simboli finiti: caratteristica che determina che il numero di simboli di ingresso e di stati sia rappresentabile da un numero finito.

Dal punto di vista pratico, il concetto di automa a stati finiti equivale a costruire un piccolo dispositivo che mediante una testina legge una stringa di input su un nastro e la elabora, facendo uso di un meccanismo molto semplice di calcolo e di una memoria limitata. L'esame della stringa avviene un carattere alla volta attraverso precisi passi computazionali che comportano l'avanzamento della testina. In sostanza un ASF è un caso particolare di macchina di Turing, utilizzato per l'elaborazione di quei linguaggi che nelle Grammatiche di Chomsky sono definiti "di tipo 3" o regolari. Distinguiamo due tipi di automi a stati finiti: gli automi a stati finiti deterministici (ASFD) e gli automi a stati finiti non deterministici (ASFND).

Automa a stati finiti deterministico

Un ASF deterministico si definisce come un sistema , dove

insieme finito dei possibili simboli in ingresso

insieme finito dei possibili simboli in uscita

insieme finito degli stati

funzione di transizione degli stati interni successivi, che collega lo stato nell'istante successivo al valore attuale dell'ingresso e dello stato,

funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato,

Automa a stati finiti non deterministico

Un ASF non deterministico si definisce come un sistema , dove

insieme finito dei possibili simboli in ingresso

insieme finito dei possibili simboli in uscita

insieme finito degli stati

funzione di transizione parziale degli stati interni successivi, che collega al valore attuale dell'ingresso e dello stato un sottoinsieme di S (quindi ad un sottoinsieme di possibili stati in S).

funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato,

Differenza tra ASFD ed ASFND

La differenza tra i due tipi di automi (già espressa dalle definizioni formali) consiste nel fatto che nei primi, in qualunque stato ci si trovi, per qualsiasi input, esisterà una ed una sola transizione, mentre nei secondi almeno uno stato presenta più di una possibile computazione per determinati caratteri in ingresso. Da notare che il determinismo è un caso particolare di non determinismo; tuttavia, nel caso degli automi a stati finiti, è possibile passare agevolmente dall'uno all'altro. L'idea è quella di unire in un unico stato collettivo [s ₁,s ₂,...,s k] gli stati s ₁,s ₂,...,s k raggiungibili con lo stesso ingresso, ovvero quelli che causano l'indeterminatezza dell'automa.

Possiamo rappresentare gli automi a stati finiti con una tabella ( tabella di transizione) o equivalentemente con una matrice (matrice di transizione). Alle righe associamo gli stati e alle colonne i simboli in input. Gli elementi della matrice rappresentano il risultato dell'applicazione della funzione di transizione.

Un'altra rappresentazione molto usata è costituita dal diagramma degli stati, o grafo di transizione, che consiste nel rappresentare l'automa mediante un grafo orientato: i nodi rappresentano gli stati e gli archi le transizioni, etichettati col simbolo di input che genera la transizione. Si può marcare lo stato iniziale con un arco entrante dal nulla e gli stati finali con un doppio circolo.

A queste rappresentazioni va aggiunta la funzione di uscita corrispondente. I diagrammi di stato saranno così modificati, come si può vedere per le macchine di Mealy e di Moore.

Un ASF può essere considerato un tipo particolare di rete di Petri.

Automa di Mealy e Automa di Moore

Nell' automa di Moore, la funzione f dipende solo dallo stato: f = S → U e dunque U(t) = f(S(t)). La macchina di Moore può essere dunque vista come una semplificazione del caso più generico, dove l'uscita dipende dallo stato e dagli ingressi. Quest'ultimo tipo di automa è detto automa di Mealy.

Gli automi finiti, o anche automi a numero di stati finito, vengono spesso chiamati in modo errato "automi a stati finiti" a causa della traduzione inglese - italiano di FSA , ma non è lo stato ad essere finito, bensì il numero degli stati. Il concetto di stato finito ricorre in meccanica quantistica e non ha nulla a che vedere con la nozione di automa finito.

SMCube - un tool gratuito per modellare, simulare e generare codice per macchine a stati finiti.

# data[].attributes.attachment_link.description
Un automa a stati finiti ( ASF o FSA, dall' inglese finite state automaton, al plurale: f. s. automata) o macchina a stati finiti ( FSM, dall'inglese finite state machine) è un tipo di automa che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi.

# data[].attributes.attachment_link.title
Artificial Intelligence Robots Development Until 2019 - Machine Learning Robot Ep. 06

# data[].attributes.headline
Automi una storia in continua evoluzione, dai singoli meccanismi, ai moderni robot e fino a Artificial Intelligence Robots

# data[].attributes.subject
Automi una storia in continua evoluzione, dai singoli meccanismi, ai moderni robot e fino a Artificial Intelligence Robots