Utente:Giuliettadome/Sandbox

Storia

Macchina computazionale

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

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 queste cinque 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").

1. le funzioni aritmetiche +, −, ×, dove− indicano "propriamente" sottrazione x − y = 0 se y ≥ x.
2. qualunque sequenza di operazioni è una operazione.
3. iterazione di un operazione (ripetere una operazione P un certo numero di volte).
4. iterazione condizionata (ripetere più volte un operazione P condizionata dal "successo" del test T).
5. trasferimento condizionato (i.e., condizionato "goto").

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 H. 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: E' 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", 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 ).

La macchina di Alan Turing

Nella primavera del 1935 Turing, da giovane studente del Master presso il King's College di Cambridge, accettò la sfida. Era stato stimolato dalle lezioni del logico M. H. A. 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:

To the question 'what is a "mechanical" process?' Turing returned the characteristic answer 'Something that can be done by a machine' and he embarked on the highly congenial task of analysing the general notion of a computing machine

—Gandy pag. 74 

Alla domanda "che cos'è un processo meccanico? " Turing ha restituito la caratteristica risposta "Qualcosa che può essere fatto da una macchina" e ha intrapreso il compito altamente congeniale di analizzare la nozione generale di una macchina informatica.

Gandy scrive:

I suppose, but do not know, that Turing, right from the start of his work, had as his goal a proof of the undecidability of the Entscheidungsproblem. He told me that the 'main idea' of the paper came to him when he was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis of computation or his realization that there was a universal machine, and so a diagonal argument to prove unsolvability (...)

— ibid., p. 76

Suppongo, ma non lo so, che Turing, fin dall'inizio del suo lavoro, avesse come obiettivo provare l'indecidibilità dell'Entscheidungsproblem. Mi disse che l'idea principale del documento gli venne in mente quando giaceva nei prati di Grantchester nell'estate del 1935. L' idea principale potrebbe essere stata la sua analisi del calcolo, o la sua realizzazione che esisteva una macchina universale e quindi un argomento diagonale per dimostrarne l'insolvibilità (...)

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"::

It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.

— Turing (1939) in The Undecidable

È stato affermato in precedenza che "una funzione è effettivamente calcolabile se i suoi valori possono essere trovati mediante un processo puramente meccanico". Possiamo prendere questa affermazione alla lettera, comprendendo un processo puramente meccanico che potrebbe essere eseguito da una macchina. È possibile fornire una descrizione matematica, in una certa forma normale, delle strutture di queste macchine. Lo sviluppo di queste idee porta alla definizione dell'autore di una funzione calcolabile e all'identificazione di calcolabilità con calcolabilità effettiva. Non è difficile, anche se un po' laborioso, dimostrare che queste tre definizioni [la terza è il calcolo λ] sono equivalenti.

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:

[that] the Hilbert Entscheidungsproblem can have no solution ... I propose, therefore to show that there can be no general process for determining whether a given formula U of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.

— The Undecidable

[che] il "problema della fermata" di Hilbert non può avere soluzione ... Propongo, quindi, di mostrare che non può esserci un processo generale per determinare se una data formula U del calcolo funzionale K è dimostrabile, cioè che non può esserci nessuna macchina che, fornita con una qualsiasi U di queste formule, alla fine dirà se U è dimostrabile.

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 in 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.

1970-oggi: la macchina di Turing come modello computazionale

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.

Confronto con le macchine reali

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 TM. Per esempio: "Una macchina di Turing può simulare ogni tipo di subroutine trovato nei linguaggi di programmazione, incluse procedure ricorsive e ogniuno dei parametri di passaggio del meccanismo conosciuti" (Hopcroft and Ullman). Anche un automa a stati finiti (FSA) sufficentemente 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 TM di manipolare una quantità illimitata di dati. Comunque, dato un tempo finito, una TM (come una macchina reale) può processare una quantità finita di dati.
3. Come una TM, 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 TM 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 ritmalgoi 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 TM semplificano i postulati degli algoritmi. Infatti algoritmi che girano su una macchina Touring-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).

Bibliografia

• Turing, A.M, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936.
• A. Hodges, Alan Turing. Storia di un Enigma, Torino, Bollati Boringhieri, 1991 [1983].
• (EN) Jackson, Philip C., Introduction to artificial intelligence.
• 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.
• (EN) John Hopcroft e Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979, ISBN 0-201-02988-X.
• Articolo divulgativo, su startmag.it.

Voci correlate

• Macchina di Turing universale
• Alan Turing