AGENZIA FEDERALE PER L'ISTRUZIONE ISTITUTO EDUCATIVO STATALE DI ISTRUZIONE PROFESSIONALE SUPERIORE "UNIVERSITÀ STATALE DI VORONEZH" T.K. Katsaran, L.N. Stroeva MACCHINA DI TURING E FUNZIONI RICORSIVE Libro di testo per università Centro editoriale e tipografico dell'Università statale di Voronezh 2008 Approvato dal consiglio scientifico e metodologico della facoltà di PMM il 25 maggio 2008, protocollo n. 9 Revisore Dottore in scienze tecniche, Prof. Dipartimento di Metodi Matematici per la Ricerca Operativa T.M. Ledeneva Il libro di testo è stato preparato presso il Dipartimento di Oscillazioni Non Lineari, Facoltà di Matematica Meccanica, Università Statale di Voronezh. Consigliato per gli studenti del 1 ° anno della Facoltà di Matematica Applicata e Matematica della VSU, rami Starooskolsky e Liskinsky della VSU. Per la specialità 010500 – Matematica applicata e informatica INTRODUZIONE La parola “algoritmo” deriva da algoritmi – la grafia latina del nome del matematico e astronomo uzbeko vissuto nei secoli VIII-IX (783–850), Muhammad ben Musa al- Khwarizmi. Il più grande matematico di Khorezm (una città nell'attuale Uzbekistan) era conosciuto con questo nome nell'Europa medievale. Nel suo libro "Sul conteggio indiano", ha formulato le regole per scrivere i numeri naturali utilizzando numeri arabi e le regole per operare su di essi. Poi il concetto di algoritmo cominciò ad essere utilizzato in un senso più ampio e non solo in matematica. Sia per i matematici che per i professionisti, il concetto di algoritmo è importante. Possiamo quindi dire che un algoritmo è una prescrizione precisa per eseguire un certo sistema di operazioni in un certo ordine per risolvere tutti i problemi dello stesso tipo, definendo una sequenza di azioni che garantisce l'ottenimento del risultato richiesto dai dati iniziali. Si noti che questa non è una definizione del concetto di “algoritmo”, ma solo la sua descrizione, il suo significato intuitivo. L'algoritmo può essere progettato per essere eseguito da una persona o da un dispositivo automatico. Questa idea di algoritmo non è rigorosa dal punto di vista matematico, poiché utilizza concetti come “istruzioni esatte” e “dati iniziali”, che, in generale, non sono strettamente definiti. Una caratteristica di qualsiasi algoritmo è la sua capacità di risolvere una determinata classe di problemi. Ad esempio, potrebbe trattarsi di un algoritmo per risolvere sistemi di equazioni lineari, trovare il percorso più breve in un grafico, ecc. Creare un algoritmo, anche il più semplice, è un processo creativo. È disponibile esclusivamente per gli esseri viventi e per molto tempo si è creduto che solo gli esseri umani. Un'altra cosa è l'implementazione di un algoritmo esistente. Può essere affidato a un soggetto o a un oggetto che non è obbligato ad approfondire l'essenza della questione, e magari non è in grado di comprenderla. Un tale soggetto o oggetto è solitamente chiamato esecutore formale. Un esempio di artista formale è una lavatrice automatica, che esegue rigorosamente le azioni prescritte, anche se ti sei dimenticato di metterci la polvere. Una persona può anche agire come esecutore formale, ma prima di tutto, vari dispositivi automatici, incluso un computer, sono esecutori formali. Ogni algoritmo è creato pensando a un artista molto specifico. Quelle azioni che l'esecutore può eseguire sono chiamate le sue azioni consentite. L'insieme delle azioni consentite forma un sistema di comandi dell'esecutore. L'algoritmo deve contenere solo le azioni consentite per un determinato artista. Pertanto, diverse proprietà generali degli algoritmi vengono solitamente formulate per distinguere gli algoritmi da altre istruzioni. L'algoritmo deve avere le seguenti proprietà. Discretezza (discontinuità, separatezza) – l'algoritmo deve rappresentare il processo di risoluzione di un problema come esecuzione sequenziale di passaggi semplici (o precedentemente definiti). Ogni azione prevista dall'algoritmo viene eseguita solo dopo che quella precedente ha completato l'esecuzione. Certezza: ogni regola dell'algoritmo deve essere chiara, inequivocabile e non lasciare spazio ad arbitrarietà. Grazie a questa proprietà, l'esecuzione dell'algoritmo è di natura meccanica e non richiede alcuna istruzione o informazione aggiuntiva sul problema da risolvere. Efficienza (finitezza) – l’algoritmo dovrebbe portare a risolvere il problema in un numero finito di passaggi. 4 Massività: l'algoritmo per risolvere il problema è sviluppato in una forma generale, cioè dovrebbe essere applicabile per una determinata classe di problemi che differiscono solo nei dati iniziali. In questo caso, i dati iniziali possono essere selezionati da una determinata area, chiamata area di applicabilità dell'algoritmo. La teoria degli algoritmi è una branca della matematica che studia le proprietà generali degli algoritmi. Esistono teorie qualitative e metriche degli algoritmi. Il problema principale della teoria qualitativa degli algoritmi è il problema di costruire un algoritmo che abbia proprietà specificate. Questo problema è chiamato problema algoritmico. La teoria metrica degli algoritmi esamina gli algoritmi in termini di complessità. Questo ramo della teoria degli algoritmi è noto anche come teoria della complessità algoritmica. Durante la ricerca di soluzioni ad alcuni problemi, è stato necessario molto tempo per trovare l'algoritmo appropriato. Esempi di tali problemi sono: a) indicare un metodo secondo il quale, per qualsiasi formula predicativa, in un numero finito di operazioni si può scoprire se è identicamente vera oppure no; b) l'equazione diofantea (un'equazione algebrica a coefficienti interi) è risolvibile in numeri interi? Poiché non è stato possibile trovare algoritmi per risolvere questi problemi, è nato il presupposto che tali algoritmi non esistessero affatto, il che è stato dimostrato: il primo problema è stato risolto da A. Church e il secondo da Yu.V. Matiyasevich e G.V. Chudnovsky. In linea di principio è impossibile dimostrarlo utilizzando il concetto intuitivo di algoritmo. Si è cercato quindi di dare una definizione matematica precisa del concetto di algoritmo. A metà degli anni '30 del XX secolo, S.K. Kleene, A.A. Markov, E. Post, A. Turing, A. Church e altri hanno proposto varie definizioni matematiche 5 del concetto di algoritmo. Successivamente è stato dimostrato che queste diverse definizioni matematiche formali sono in un certo senso equivalenti: calcolano lo stesso insieme di funzioni. Ciò suggerisce che le caratteristiche principali del concetto intuitivo di algoritmo sembrano essere correttamente catturate in queste definizioni. Successivamente, consideriamo un perfezionamento matematico dell'algoritmo proposto da A. Turing, che viene chiamato macchina di Turing. 6 1. MACCHINA DI TURING § 1. Modello matematico della macchina di Turing L'idea di creare una macchina di Turing, proposta dal matematico inglese A. Turing negli anni Trenta del XX secolo, è legata al suo tentativo di dare una precisa definizione matematica del concetto di algoritmo. Una macchina di Turing (MT) è un modello matematico di un computer digitale idealizzato. Una macchina di Turing è lo stesso oggetto matematico di una funzione, derivata, integrale, gruppo, ecc. Proprio come altri concetti matematici, il concetto di macchina di Turing riflette la realtà oggettiva e modella determinati processi reali. Per descrivere l'algoritmo MT è conveniente immaginare un dispositivo composto da quattro parti: nastro, testina di lettura, dispositivo di controllo e memoria interna. 1. Si presuppone che il nastro sia potenzialmente infinito, suddiviso in celle (celle uguali). Se necessario, alla prima o all'ultima cella in cui si trovano i simboli viene allegata una cella vuota. La macchina opera nel tempo, che è considerato discreto, e i suoi momenti sono numerati 1, 2, 3, …. In ogni istante il nastro contiene un numero finito di celle. Solo un simbolo (lettera) dell'alfabeto esterno A = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 può essere scritto nelle celle in un momento discreto. Una cella vuota è designata dal simbolo L e il simbolo L stesso è chiamato vuoto, mentre i simboli rimanenti sono chiamati non vuoti. In questo alfabeto A, l'informazione fornita al MT è codificata sotto forma di parola (un insieme finito e ordinato di simboli). La macchina “elabora” le informazioni presentate sotto forma di parola in una nuova parola. 2. La testina di lettura (un certo elemento di lettura) si muove lungo il nastro in modo tale che in ogni momento visualizzi esattamente una cella del nastro. La testa può leggere il contenuto di una cella e scrivervi un nuovo carattere dell'alfabeto A. In un ciclo di operazioni, può spostarsi solo di una cella a destra (R), a sinistra (L) o rimanere sul posto (N ). Indichiamo l'insieme dei movimenti (spostamenti) della testa D = (P, L, N). Se in un dato momento t la testa si trova nella cella più esterna e si sposta nella cella mancante, viene aggiunta una nuova cella vuota, sopra la quale la testa si troverà al momento t + 1. 3. La memoria interna della macchina è un certo insieme finito di stati interni Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 . Assumeremo che la potenza |Q | ³ 2. Due stati della macchina hanno un significato speciale: q1 è lo stato interno iniziale (possono esserci diversi stati interni iniziali), q0 è lo stato finale o stato di arresto (c'è sempre uno stato finale). In ogni momento, la MT è caratterizzata dalla posizione della testa e dallo stato interno. Ad esempio, sotto la cella sopra la quale si trova la testa, è indicato lo stato interno della macchina. ¯ a2 a1 L a2 a3 q1 4. In ogni momento t, il dispositivo di controllo, a seconda del simbolo presente sul nastro letto in quel momento e dello stato interno della macchina, esegue le seguenti azioni: 1) cambia il simbolo ai letto al momento t ad un nuovo simbolo a j (in particolare, lo lascia invariato, cioè ai = a j); 2) muove la testa in una delle seguenti direzioni: N, L, R; 3) cambia lo stato interno della macchina 8 qi esistente al momento t in un nuovo q j in cui la macchina si troverà al tempo t +1 (potrebbe essere che qi = q j). Tali azioni del dispositivo di controllo sono chiamate comando, che può essere scritto nella forma: qi ai ® a j D q j , (1) dove qi è lo stato interno della macchina in questo momento; a i – il simbolo letto in questo momento; a j – il simbolo in cui cambia il simbolo a i (può essere ai = a j); il simbolo D è N, oppure L, oppure P e indica la direzione del movimento della testa; q j è lo stato interno della macchina nel momento successivo (forse qi = q j). Le espressioni qi ai e a j D q j sono chiamate rispettivamente i lati sinistro e destro di questo comando. Il numero di comandi in cui i membri di sinistra sono distinti a due a due è un numero finito, poiché gli insiemi Q \ (q 0 ) e A sono finiti. Non ci sono comandi con la stessa parte sinistra, cioè se il programma della macchina T contiene le espressioni qi ai ® a j D q j e qt at ® ak D qk , allora qi ¹ qt o ai ¹ at e D O (P, L, N ). L’insieme di tutte le istruzioni è chiamato programma della macchina di Turing. Il numero massimo di comandi in un programma è (n + 1) x m, dove n + 1 = A e m + 1 = Q. Si ritiene che lo stato finale del comando q0 possa apparire solo sul lato destro del comando, lo stato iniziale q1 possa apparire sia sul lato sinistro che su quello destro del comando. L'esecuzione di un comando è chiamata passo. Il calcolo (o il funzionamento) di una macchina di Turing è una sequenza di passaggi uno dopo l'altro senza saltare, a partire dal primo. Quindi, MT è dato se si conoscono quattro insiemi finiti: l'alfabeto esterno A, l'alfabeto interno Q, l'insieme D dei movimenti della testa e il programma della macchina, che è un insieme finito di comandi. 9 § 2. Funzionamento di una macchina di Turing Il funzionamento della macchina è completamente determinato dal compito nel primo momento (iniziale): 1) parole sul nastro, cioè una sequenza di simboli scritti nelle celle del nastro (a la parola si ottiene leggendo questi simboli attraverso le celle del nastro da sinistra a destra); 2) posizione della testa; 3) lo stato interno della macchina. La combinazione di queste tre condizioni (al momento) si chiama configurazione (al momento). Tipicamente, nel momento iniziale, lo stato interno della macchina è q1 e la testina si trova sopra la prima cella sinistra o la prima cella destra del nastro. Una data parola sul nastro con stato iniziale q1 e posizione della testina sopra la prima parola è chiamata configurazione iniziale. Altrimenti diremo che la macchina di Turing non è applicabile ad una parola di configurazione iniziale. In altre parole, al momento iniziale la configurazione è rappresentabile nella seguente forma: su un nastro costituito da un certo numero di celle, in ciascuna cella è scritto uno dei simboli dell'alfabeto esterno A, la testa si trova sopra la prima cella sinistra o prima destra del nastro e quella interna.la posizione della macchina è q1. La parola risultante sulla posizione del nastro e della testina risultante dall'implementazione di questo comando è chiamata configurazione finale. Ad esempio, se al momento iniziale sul nastro è scritta la parola a1La 2 a1a1, la configurazione iniziale sarà simile a: a1 a2 L a1 a1 q1 (sotto la cella sopra la quale si trova la testina, lo stato interno della macchina è indicato). 10

Argomento “Macchina di Turing” in un corso di informatica scolastica

IN. Falina,
Mosca

In molti libri di testo di informatica, quando si studia il concetto e le proprietà di un algoritmo, ci sono frasi con il seguente contenuto: “... ci sono molti modi diversi per scrivere lo stesso algoritmo, ad esempio scrivendo sotto forma di testo, scrivendo sotto forma di diagramma di flusso, scrittura in un linguaggio algoritmico, rappresentazione di un algoritmo sotto forma di macchina di Turing o di Post machine...” Sfortunatamente, questo tipo di frasi sono le uniche che menzionano una macchina di Turing. Senza dubbio, il volume di ore dedicate allo studio degli algoritmi non ci consente di includere in questo argomento anche lo studio dei modi per scrivere un algoritmo sotto forma di macchina di Turing. Ma questo argomento è estremamente interessante, importante e utile per gli scolari, soprattutto per quelli interessati all'informatica.

L'argomento "Macchina di Turing" può essere studiato nelle classi 8-11 come parte dell'argomento "Processi di informazione. Elaborazione delle informazioni”, nelle classi opzionali, nel sistema di istruzione aggiuntiva, ad esempio, nelle scuole per giovani programmatori. Lo studio di questo argomento può essere accompagnato dal supporto informatico se il docente dispone di un simulatore software “Turing Machine”. Nelle lezioni di programmazione avanzata, gli studenti possono scrivere autonomamente un programma di Turing Machine. Nell'ambito di questo articolo vi offriamo un workshop sulla risoluzione dei problemi sull'argomento “Macchina di Turing”. Materiale teorico su questo argomento è stato pubblicato più di una volta sulle pagine del quotidiano Informatics, ad esempio nel n. 3/2004, un articolo di I.N. Falina “Elementi di teoria degli algoritmi”.

Una macchina di Turing è una costruzione matematica rigorosa, un apparato matematico (simile, ad esempio, all'apparato delle equazioni differenziali), creato per risolvere determinati problemi. Questo apparato matematico è stato chiamato “macchina” perché, in termini di descrizione delle sue parti costitutive e del funzionamento, è simile a un computer. La differenza fondamentale tra una macchina di Turing e i computer è che il suo dispositivo di memorizzazione è un nastro infinito: nei computer reali, il dispositivo di memorizzazione può essere grande quanto si desidera, ma deve essere finito. Una macchina di Turing non può essere realizzata proprio perché il suo nastro è infinito. In questo senso è più potente di qualsiasi macchina informatica.

Ogni macchina di Turing è composta da due parti:

1)illimitato andata e ritorno nastro, diviso in celle;

2) macchina(testina di lettura/scrittura controllata da software).

Ogni macchina di Turing è associata a due alfabeti finali: alfabeto dei simboli di input A = (a 0 , a 1 , ..., am ) e alfabeto degli stati Q = (q 0 , q 1 , ..., q p ). (Diverse macchine di Turing possono avere diversi alfabeti associati ad esse UN E Q.) Viene chiamato lo stato q 0 passivo. Si ritiene che se la macchina entra in questo stato, allora ha terminato il suo lavoro. Viene chiamato lo stato q 1 iniziale. Mentre è in questo stato, la macchina inizia il suo lavoro.

La parola immessa viene posizionata sul nastro una lettera alla volta in celle consecutive. A sinistra e a destra della parola inserita ci sono solo celle vuote (nell'alfabeto UN include sempre una lettera vuota UN 0 è un segno che la cella è vuota).

La macchina può spostarsi lungo il nastro a sinistra o a destra, leggere il contenuto delle celle e scrivere lettere nelle celle. Di seguito è riportato un disegno schematico di una macchina di Turing, il cui automa esamina la prima cella con i dati.

La macchina “vede” solo una cella alla volta. A seconda di quale lettera ai vede, e anche a seconda delle sue condizioni qj La macchina può eseguire le seguenti azioni:

• · scrivere una nuova lettera nella cella osservata;
• · spostare il nastro di una cella a destra/sinistra o restare immobile;
• · trasferirsi in un nuovo stato.

Cioè, una macchina di Turing ha tre tipi di operazioni. Ogni volta per la coppia successiva ( qj, un io) una macchina di Turing esegue un comando composto da tre operazioni con determinati parametri.

Il programma della macchina di Turing è una tabella con un comando scritto in ogni cella.

Cellula ( qj, un io) è determinato da due parametri: il simbolo dell'alfabeto e lo stato della macchina. Il comando è un'indicazione: dove spostare la testina di lettura/scrittura, quale carattere scrivere nella cella corrente, in quale stato deve portarsi la macchina. Per indicare la direzione di movimento della macchina, utilizziamo una delle tre lettere: “L” (sinistra), “P” (destra) o “N” (stazionario).

Dopo che la macchina ha eseguito il comando successivo, entra nello stato qm(che in un caso particolare può coincidere con lo stato precedente qj). Il comando successivo dovrebbe essere trovato in M l'esima riga della tabella all'intersezione con la colonna al(lettera al la macchina vede dopo il turno).

Conveniamo che quando il nastro contiene una parola di input, la macchina si trova contro una cella nello stato Q 1. Durante il funzionamento, l'automa salterà da una cella all'altra del programma (tabella) fino a raggiungere la cella in cui è scritto che l'automa dovrebbe entrare nello stato Q 0 . Queste cellule sono chiamate fermare le cellule. Dopo aver raggiunto una cella di questo tipo, la macchina di Turing fermate.

Nonostante la sua struttura semplice, una macchina di Turing può eseguire tutte le possibili trasformazioni delle parole, implementando così tutti i possibili algoritmi.

Esempio. Devi costruire una macchina di Turing che aggiunga uno a un numero su un nastro. La parola in ingresso è costituita dalle cifre intere decimali scritte in celle consecutive sul nastro. Nel momento iniziale, la macchina si trova di fronte alla cifra più a destra del numero.

Soluzione. La macchina deve aggiungere uno all'ultima cifra del numero. Se l'ultima cifra è 9, sostituiscila con 0 e aggiungi uno alla cifra precedente. Un programma per una determinata macchina di Turing potrebbe assomigliare a questo:

In questa macchina di Turing Q Stato di modifica di 1 cifra, Q 0 - stato di arresto. Se potete ql la macchina vede il numero 0..8, poi lo sostituisce rispettivamente con 1..9 ed entra nello stato Q 0, cioè la macchina si ferma. Se vede il numero 9, lo sostituisce con 0, si sposta a sinistra, rimanendo nello stato ql. Questo continua finché la macchina non incontra un numero inferiore a 9. Se tutti i numeri fossero uguali a 9, li sostituirà con zeri, scriverà 0 al posto della cifra più alta, si sposterà a sinistra e scriverà 1 in una cella vuota. Poi passerà allo Stato Q 0, cioè smetterò.

Compiti pratici

1. Il nastro della macchina di Turing contiene una sequenza di simboli “+”. Scrivi un programma per una macchina di Turing che sostituisca ogni secondo simbolo “+” con un “–”. La sostituzione inizia dall'estremità destra della sequenza. La macchina è capace Q 1 guarda uno dei caratteri nella sequenza specificata. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

2. Dato un numero N nel sistema numerico ottale. Progetta una macchina di Turing che incrementi un dato numero N a 1. La macchina è in grado Q 1 esamina una determinata cifra della parola di input. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

3. Data la notazione decimale di un numero naturale N> 1. Sviluppare una macchina di Turing che riduca un dato numero N a 1. La macchina è in grado Q 1 guarda la cifra destra del numero. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

4. Dato un numero naturale N> 1. Sviluppare una macchina di Turing che riduca un dato numero N per 1, mentre la cifra più significativa nella parola di uscita non dovrebbe essere 0. Ad esempio, se la parola di ingresso era “100”, allora la parola di uscita dovrebbe essere “99”, non “099”. La macchina è capace Q 1 guarda la cifra destra del numero. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

5. Dato un array di parentesi di apertura e chiusura. Costruisci una macchina di Turing che rimuova le coppie di parentesi reciproche, ad es. situato nella riga “()”.

Ad esempio, dato “) (() (()”, è necessario ottenere “) . . . ((”.

La macchina è capace Q

6. Data una stringa di lettere “ UN" E " B" Sviluppare una macchina di Turing che sposterà tutte le lettere” UN" a sinistra e le lettere " B" - sul lato destro della linea. La macchina è capace Q 1 esamina il carattere più a sinistra della riga. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

7. Sul nastro della macchina di Turing c'è un numero scritto nel sistema decimale. Moltiplicare questo numero per 2. La macchina è in grado Q 1 guarda la cifra più a sinistra del numero. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

8. Dati due numeri naturali M E N, presentato nel sistema numerico unario. I set di caratteri corrispondenti sono "|" separati da una cella vuota. La macchina è capace Q 1 esamina il carattere più a destra della sequenza di input. Sviluppa una macchina di Turing che lasci una somma di numeri su un nastro M E N. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

9. Dati due numeri naturali M E N, presentato nel sistema numerico unario. I set di caratteri corrispondenti sono "|" separati da una cella vuota. La macchina è capace Q 1 esamina il carattere più a destra della sequenza di input. Sviluppa una macchina di Turing che lasci una differenza tra i numeri sul nastro. M E N. È risaputo che M> N. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

10. C'è un numero decimale sul nastro della macchina di Turing. Determina se questo numero è divisibile per 5 senza resto. Se è divisibile, scrivi la parola "sì" a destra del numero, altrimenti "no". La macchina esamina una certa cifra del numero inserito. Oltre alla tabella del programma stesso, descrivi a parole cosa viene eseguito dalla macchina in ogni stato.

Capace Q 1 macchina cerca l'estremità destra del numero, capace Q 2 - salta il segno “+”, quando arriva alla fine della sequenza - si ferma. Capace Q 3, la macchina sostituisce il segno “+” con il segno “–” e quando arriva alla fine della sequenza si ferma.

La soluzione a questo problema è simile all'esempio discusso sopra.

Stato Q 1 - diminuiamo la cifra più bassa (successiva) di 1. Se non è uguale a zero, ci fermiamo immediatamente dopo la diminuzione; se la cifra più bassa è 0, scriviamo invece 9, spostiamo a sinistra ed eseguiamo nuovamente la sottrazione . In una gabbia [ UN 0 , Q 1] una macchina di Turing non colpirà mai, quindi può essere lasciata vuota.

Compito 4 (complicazione del compito 3)

Stato Q 1 - diminuiamo la cifra minore (successiva) di 1. Se è maggiore di 1, dopo la riduzione ci fermiamo immediatamente, ma se la cifra minore è 0, scriviamo invece 9, spostiamo a sinistra ed eseguiamo la sottrazione Ancora. Se la cifra da ridurre è 1, scriviamo invece 0 e passiamo allo stato Q 2 .

Stato Q 2 - dopo aver scritto “0” in qualsiasi posizione, è necessario analizzare se questo zero è la cifra più significativa (cioè se si trova alla sua sinistra nel record della parola di uscita UN 0).

Stato Q 3 - se lo “0” registrato è la cifra più significativa, allora deve essere rimosso dal record della parola di uscita.

Quelle celle in cui la macchina di Turing non entra mai vengono lasciate vuote.

Stato Q 1: se si incontra “(”, spostarsi a destra e andare allo stato Q 2; se ti incontrassi” UN 0", quindi fermarsi.

Stato Q 2: analisi del simbolo “(” per abbinamento, in caso di abbinamento dovrebbe vedere “)”. Se è un bagno turco, torna a sinistra e vai allo stato Q 3 .

Stato Q 3: prima cancella “(”, poi “)” e vai a Q 1 .

Risolvere questo problema di solito causa difficoltà agli scolari. Quando analizzi la soluzione a questo problema, puoi procedere, ad esempio, nel modo seguente.

Esamina le seguenti opzioni per le parole di input con i tuoi studenti e chiedi loro di formulare cosa dovrebbe fare una macchina di Turing, come appare la parola di output e come queste opzioni differiscono dal punto di vista di una macchina di Turing:

aaa ->

a -> la parola di output corrisponde alla parola di input, esaminiamo la parola di input finché non finisce.

bbb -> la parola di output corrisponde alla parola di input, esaminiamo la parola di input finché non finisce.

b -> la parola di output corrisponde alla parola di input, esaminiamo la parola di input finché non finisce.

ab -> la parola di output corrisponde alla parola di input, esaminiamo la parola di input finché non finisce.

Risultato della discussione. Una macchina di Turing deve “capire” quale catena di lettere segue, cioè deve avere almeno due stati. Lasciamo lo Stato Q 1 - movimento lungo una catena di lettere “ UN", UN Q 2 - stato di movimento lungo una catena di lettere “ B" Tieni presente che la catena può essere composta anche da una lettera. Se siamo arrivati ​​al capolinea nello Stato Q 1 o Q 2, cioè incontrato UN 0 , la macchina dovrebbe fermarsi, abbiamo elaborato l'intera linea.

Considera le seguenti opzioni per le parole di input:

bba -> abb

bbbaab -> aabbbb

aabbbaab -> aaaabbbb

Risultato della discussione. La prima versione della parola di ingresso può essere elaborata in sequenza come segue: bba -> bbb-> torna all'estremità sinistra della catena di lettere “ B” -> abb(sostituisci la prima lettera di questa catena con “ UN"). Per eseguire queste azioni, dovremo introdurre due nuovi stati e, inoltre, chiarire lo stato Q 2. Pertanto, per risolvere questo problema dobbiamo costruire una macchina di Turing con i seguenti stati:

q 1 - vai a destra lungo la catena di lettere “ UN" Se la catena finisce UN 0, quindi vai a Q 0; se termina con la lettera “ B”, poi andiamo a Q 2 ;

q 2 - vai a destra lungo la catena di lettere “ B” se la catena finisce UN 0, quindi vai a Q 0; se finisce” UN", quindi sostituire la lettera " UN" SU " B”, vai allo Stato Q 3 (la catena delle specie è stata sostituita con una catena delle specie);

q 3 - vai a sinistra lungo la catena di lettere “ B" alla sua estremità sinistra. Se ti incontrassi UN 0 o “ UN”, poi andiamo a Q 4 ;

q 4 - sostituire “ B" SU " UN” e vai a Q 1 (sostituire la catena del form con una catena del form .

Problema 7

stato Q 1 - cerca la cifra destra (più bassa) di un numero;

stato Q 2 - moltiplicare la cifra successiva di un numero per 2 senza aggiungere 1 riporto;

stato Q 3 - moltiplicando la cifra successiva di un numero per 2 con l'aggiunta di 1 riporto.

La macchina di Turing per questo programma sembra banalmente semplice: ha un solo stato. Una macchina di Turing di questo tipo esegue le seguenti azioni: cancella il tratto più a destra, cerca un separatore (cella vuota) e inserisce un tratto in questa cella vuota, formando così una sequenza continua di tratti di lunghezza N + M.

Tuttavia, stranamente, la soluzione di questo problema causa grandi difficoltà. Molto spesso gli studenti costruiscono una macchina di Turing che esegue azioni cicliche: spingendo in sequenza verso destra N colpi a sinistra.

In questo caso, il loro programma assomiglia a questo:

stato Q 1 - cerca separatore;

stato Q 2 - spostato il tratto;

stato Q 3 - verificare la fine (se tutti i tratti sono stati spostati).

L'esempio di questo problema mostra chiaramente quanto spesso i bambini cercano di risolvere un problema in modi già familiari. Mi sembra che offrendo agli studenti problemi per costruire macchine di Turing, sviluppiamo la capacità di trovare soluzioni insolite e sviluppiamo la capacità di pensare in modo creativo!

Questo compito sembra abbastanza facile per gli scolari, ma sorgono difficoltà quando si ferma la macchina di Turing. Di seguito è riportata una possibile versione di una macchina di Turing per questo compito.

Idea di soluzione (condizione di stop). Sul nastro sono presenti due array di tratti iniziali.

Iniziamo a cancellare i tratti dall'estremità sinistra dell'array M. E uno per uno cancelliamo il tratto più a sinistra dell'array M e il tratto più a destra dell'array N. Ma prima di cancellare il tratto giusto nell'array N, controlliamo se è l'unico (cioè l'ultimo da cancellare) oppure no.

Descriviamo prima gli stati della macchina di Turing necessari per risolvere il nostro problema, quindi creiamo un programma tabellare.

Stato Q 1 - cerca un separatore tra serie di tratti quando ti sposti da destra a sinistra;

stato Q 2 - cerca il tratto sinistro nell'array M;

stato Q 3 - rimozione del tratto sinistro nell'array M;

stato Q 4 - cerca un separatore quando ti sposti da sinistra a destra;

stato Q 5 - cerca il tratto giusto nell'array N;

stato Q 6 - verifica dell'unicità di questo tratto nell'array N, cioè. determinare se era l'ultimo;

stato Q 7 - se fosse l'ultimo, allora interrompi, altrimenti vai a un nuovo ciclo di esecuzione dell'algoritmo.

Quando risolvi questo problema, dovresti prestare attenzione alla corretta scrittura dell'alfabeto:

UN = ( UN 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, D, A, N, E, T).

Stato Q 1 - cerca l'estremità destra del numero;

stato Q 2 - analisi della cifra meno significativa del numero; se è uguale a “0” o “5”, cioè il numero è divisibile per 5, quindi il passaggio allo stato Q 3 , altrimenti passaggio allo stato Q 5 ;

stato Q 3 - scrivere la lettera “D” a destra della parola sul nastro;

stato Q 4 - scrivere la lettera “A” a destra della parola e fermare la macchina;

stato Q 5 - scrivere la lettera “N” a destra della parola;

stato Q 6 - scrivere la lettera “E” a destra della parola;

stato Q 7 - scrivere la lettera “T” a destra della parola e fermare la macchina.

Proprietà della macchina di Turing come algoritmo

Usando la macchina di Turing come esempio, le proprietà degli algoritmi possono essere viste chiaramente. Chiedi agli studenti di dimostrare che una macchina di Turing ha tutte le proprietà di un algoritmo.

Discrezione. Una macchina di Turing può andare a ( k+ 1)esimo passaggio solo dopo il completamento A- l'esimo passo, perché esattamente A- L'esimo passaggio determina cosa sarà ( k+ 1)esimo passo.

Chiarezza. Ad ogni passo, un simbolo dell'alfabeto viene scritto nella cella, l'automa esegue un movimento (L, P, N) e la macchina di Turing entra in uno degli stati descritti.

Determinismo. Ogni cella della tabella della macchina di Turing contiene solo un'opzione per un'azione. Ad ogni passaggio, il risultato è determinato in modo univoco, pertanto, la sequenza dei passaggi per risolvere il problema è determinata in modo univoco, ad es. Se a una macchina di Turing viene assegnata la stessa parola di input, la parola di output sarà ogni volta la stessa.

Produttività. In termini di contenuto, i risultati di ogni passaggio e l’intera sequenza di passaggi sono definiti in modo univoco; pertanto, una macchina di Turing scritta correttamente entrerà nello stato in un numero finito di passaggi Q 0, cioè in un numero finito di passaggi si otterrà la risposta alla domanda del problema.

Carattere di massa. Ogni macchina di Turing è definita su tutte le parole ammissibili dell'alfabeto, questa è la proprietà del carattere di massa. Ogni macchina di Turing è progettata per risolvere una classe di problemi, cioè Per ogni problema viene scritta la propria (nuova) macchina di Turing.

DALL'EDITORE

Tutti i problemi indicati nell'articolo possono essere risolti semplicemente su un quaderno disegnando una striscia informativa e un programma da tavolo. Ma puoi rendere questo processo più divertente e visivo: usa un'implementazione della macchina - l'interprete della macchina Post e della macchina di Turing “Algo2000”, creata da Radik Zartdinov. Il programma ha un'interfaccia intuitiva e le sue esigenze sono le più moderate: un computer IBM PC AT 486 o superiore, il sistema operativo Windows 95/98/NT.

Vediamo in termini generali come funziona “Algo2000”.

Nel menu del programma, selezionare la voce Interprete e indicare con quale macchina vogliamo lavorare (nel nostro caso è una “macchina di Turing”).

Davanti a noi apparirà un campo di macchina di Turing.

Ora devi impostare l'alfabeto esterno, ad es. in linea Alfabeto esterno indicare quali caratteri sono inclusi al suo interno (se la stringa Alfabeto esterno non visibile, è necessario selezionare una voce di menu Visualizza | Alfabeto esterno). Ogni carattere può essere specificato solo una volta. Dopo aver terminato l'inserimento dell'alfabeto esterno, si forma la prima colonna della tabella: viene riempita con i caratteri dell'alfabeto esterno nello stesso ordine. Quando si modifica l'alfabeto esterno, la tabella viene modificata automaticamente: le righe vengono inserite, cancellate o scambiate.

Non dimentichiamo che devi in ​​qualche modo disporre i simboli dell'alfabeto esterno in sezioni del nastro (puoi lasciare tutte le sezioni vuote) e posizionare il carrello di fronte a una delle sezioni, ad es. è necessario impostare il programma e alcuni stati della macchina.

Ora puoi procedere direttamente alla scrittura dell'algoritmo per risolvere il problema. È specificato sotto forma di tabella: i caratteri dell'alfabeto interno vengono inseriti in ciascuna colonna della riga superiore e i caratteri dell'alfabeto esterno vengono inseriti in ciascuna riga della prima colonna. I comandi vengono inseriti nelle celle all'intersezione di altre colonne e righe. Se all'intersezione di qualsiasi riga e colonna otteniamo una cella vuota, significa che in questo stato interno questo simbolo non può essere trovato.

Ad esempio, stiamo creando un algoritmo per trovare la differenza tra due numeri interi positivi (nel sistema decimale), se è noto che il primo numero è maggiore del secondo e tra di loro c'è un segno meno.

Il campo del programma sarà simile a questo:

Il formato del comando in ogni cella è aKq. Qui:
a è il nuovo contenuto della cella corrente (un nuovo simbolo dell'alfabeto esterno che viene inserito nella cella corrente), K è il comando del meccanismo a nastro della macchina di Turing (sinistra, destra, stop), q è il nuovo stato interno della macchina di Turing.

Il pulsante avvierà il programma. Se l'esecuzione non è stata sospesa, inizia sempre dallo stato interno zero Q0.

Il programma può essere completato passo dopo passo. Per fare ciò, fare clic sul pulsante sulla barra degli strumenti (se i pulsanti non sono visibili, è necessario selezionare la voce di menu Visualizza | Barra degli strumenti) o selezionarlo dal menu principale Inizio | Passo dopo passo. Se è necessario interrompere completamente l'esecuzione del programma, è possibile farlo utilizzando il pulsante sulla barra degli strumenti o utilizzando il menu principale ( Inizio | Interrompere). Elemento del menu Velocità consente di regolare la velocità di esecuzione del programma.

Il programma continuerà l'esecuzione finché non verrà rilevato il comando "Stop" o si verificherà qualche errore.

In caso di domande mentre si lavora con il programma interprete, fare riferimento al file della guida Algo2000.hlp. Esso, così come lo stesso programma “Algo2000”, può essere trovato sul sito web del quotidiano “Informatica” http://inf.1september.ru nella sezione “Scarica”.

Intelligenza artificiale (AI, inglese: Intelligenza artificiale, AI) - la scienza e la tecnologia per la creazione di macchine intelligenti, in particolare programmi per computer intelligenti. L’intelligenza artificiale è legata al compito simile di utilizzare i computer per comprendere l’intelligenza umana, ma non è necessariamente limitata a metodi biologicamente plausibili.

Cos'è l'intelligenza artificiale

Intelligenza(dal lat. intellectus - sensazione, percezione, comprensione, comprensione, concetto, ragione), o mente - una qualità della psiche costituita dalla capacità di adattarsi a nuove situazioni, la capacità di apprendere e ricordare in base all'esperienza, comprendere e applicare concetti astratti e utilizzare le proprie conoscenze per la gestione ambientale. L'intelligenza è la capacità generale di cognizione e di risoluzione delle difficoltà, che unisce tutte le capacità cognitive umane: sensazione, percezione, memoria, rappresentazione, pensiero, immaginazione.

All'inizio degli anni '80. Gli scienziati computazionali Barr e Fajgenbaum hanno proposto la seguente definizione di intelligenza artificiale (AI):

Successivamente, una serie di algoritmi e sistemi software iniziarono a essere classificati come IA, la cui proprietà distintiva è che possono risolvere alcuni problemi nello stesso modo in cui lo farebbe una persona che pensa alla loro soluzione.

Le principali proprietà dell’intelligenza artificiale sono la comprensione del linguaggio, l’apprendimento e la capacità di pensare e, soprattutto, di agire.

L'intelligenza artificiale è un complesso di tecnologie e processi correlati che si stanno sviluppando qualitativamente e rapidamente, ad esempio:

• elaborazione del testo in linguaggio naturale
• sistemi esperti
• agenti virtuali (chatbot e assistenti virtuali)
• sistemi di raccomandazione.

Strategia nazionale per lo sviluppo dell’intelligenza artificiale

• Articolo principale: Strategia nazionale per lo sviluppo dell’intelligenza artificiale

Ricerca sull'intelligenza artificiale

• Articolo principale: Ricerca sull'intelligenza artificiale

Standardizzazione nell'intelligenza artificiale

2019: gli esperti ISO/IEC sostengono la proposta di sviluppare uno standard in russo

Il 16 aprile 2019 si è appreso che il sottocomitato ISO/IEC per la standardizzazione nel campo dell’intelligenza artificiale ha sostenuto la proposta del comitato tecnico “Sistemi ciberfisici”, creato sulla base dell’RVC, per sviluppare l’“Intelligenza artificiale” standard. Concetti e terminologia" in russo oltre alla versione base in inglese.

Standard terminologico “Intelligenza artificiale. Concetti e terminologia" è fondamentale per l'intera famiglia di documenti normativi e tecnici internazionali nel campo dell'intelligenza artificiale. Oltre a termini e definizioni, questo documento contiene approcci concettuali e principi per la costruzione di sistemi con elementi, una descrizione della relazione tra l'intelligenza artificiale e altre tecnologie end-to-end, nonché principi di base e approcci quadro alla regolamentazione normativa e tecnica dell'intelligenza artificiale.

Dopo l'incontro del sottocomitato ISO/IEC competente a Dublino, gli esperti ISO/IEC hanno sostenuto la proposta della delegazione russa di sviluppare contemporaneamente uno standard terminologico nel campo dell'intelligenza artificiale non solo in inglese, ma anche in russo. Si prevede che il documento venga approvato all’inizio del 2021.

Durante l'incontro, gli esperti ISO/IEC hanno anche sostenuto lo sviluppo di una bozza di documento internazionale Information Technology - Artificial Intelligence (AI) - Overview of Computational Approaches for AI Systems, in cui la Russia funge da co-editore. Il documento fornisce una panoramica dello stato attuale dei sistemi di intelligenza artificiale, descrivendo le principali caratteristiche dei sistemi, degli algoritmi e degli approcci, nonché esempi di applicazioni specializzate nel campo dell’IA. Lo sviluppo di questa bozza di documento sarà effettuato da un gruppo di lavoro 5 appositamente creato “Approcci computazionali e caratteristiche computazionali dei sistemi di intelligenza artificiale” all’interno del sottocomitato (SC 42 Gruppo di lavoro 5 “Approcci computazionali e caratteristiche computazionali dei sistemi di intelligenza artificiale”).

Le tecnologie di intelligenza artificiale sono molto richieste in diversi settori dell’economia digitale. Tra i principali fattori che ne ostacolano l’uso pratico su vasta scala c’è il sottosviluppo del quadro normativo. Allo stesso tempo, è il quadro normativo e tecnico ben sviluppato che garantisce la qualità specifica dell’applicazione tecnologica e il corrispondente effetto economico.

Nel campo dell’intelligenza artificiale, TC Cyber-Physical Systems, sulla base di RVC, sta sviluppando una serie di standard nazionali, la cui approvazione è prevista per la fine del 2019 – inizio del 2020. Inoltre, sono in corso lavori insieme agli attori del mercato per formulare un Piano Nazionale di Standardizzazione (NSP) per il 2020 e oltre. Il TC "Sistemi ciberfisici" è aperto a proposte per lo sviluppo di documenti da parte di organizzazioni interessate.

2018: Sviluppo di standard nel campo delle comunicazioni quantistiche, dell'intelligenza artificiale e delle smart city

Il 6 dicembre 2018, il comitato tecnico “Sistemi ciberfisici” basato su RVC insieme al Centro regionale di ingegneria “SafeNet” ha iniziato a sviluppare una serie di standard per i mercati dell’Iniziativa tecnologica nazionale (NTI) e dell’economia digitale. Entro marzo 2019 si prevede di sviluppare documenti di standardizzazione tecnica nel campo delle comunicazioni quantistiche, ha riferito RVC. Per saperne di più.

Impatto dell'intelligenza artificiale

Rischio per lo sviluppo della civiltà umana

Impatto sull’economia e sulle imprese

• L’impatto delle tecnologie di intelligenza artificiale sull’economia e sul business

Impatto sul mercato del lavoro

Bias dell’intelligenza artificiale

Al centro di tutto ciò che costituisce la pratica dell’intelligenza artificiale (traduzione automatica, riconoscimento vocale, elaborazione del linguaggio naturale, visione artificiale, guida automatizzata e molto altro) c’è il deep learning. Si tratta di un sottoinsieme dell'apprendimento automatico, caratterizzato dall'uso di modelli di reti neurali, che si può dire imitano il funzionamento del cervello, quindi sarebbe eccessivo classificarli come IA. Qualsiasi modello di rete neurale viene addestrato su grandi set di dati, quindi acquisisce alcune “competenze”, ma il modo in cui le utilizza rimane poco chiaro ai suoi creatori, il che alla fine diventa uno dei problemi più importanti per molte applicazioni di deep learning. Il motivo è che un modello del genere funziona formalmente con le immagini, senza alcuna comprensione di ciò che fa. Un sistema del genere è AI e i sistemi basati sull’apprendimento automatico sono affidabili? Le implicazioni della risposta all’ultima domanda si estendono oltre il laboratorio scientifico. Pertanto, l’attenzione dei media sul fenomeno chiamato AI bias si è notevolmente intensificata. Può essere tradotto come “bias AI” o “bias AI”. Per saperne di più.

Mercato della tecnologia dell’intelligenza artificiale

Il mercato dell’intelligenza artificiale in Russia

Il mercato globale dell’intelligenza artificiale

Aree di applicazione dell'IA

Gli ambiti di applicazione dell'intelligenza artificiale sono piuttosto ampi e coprono sia le tecnologie familiari che i nuovi settori emergenti lontani dall'applicazione di massa, in altre parole si tratta dell'intera gamma di soluzioni, dagli aspirapolvere alle stazioni spaziali. Puoi dividere tutta la loro diversità secondo il criterio dei punti chiave dello sviluppo.

L’intelligenza artificiale non è un argomento monolitico. Inoltre, alcune aree tecnologiche dell’IA appaiono come nuovi sottosettori dell’economia ed entità separate, servendo contemporaneamente la maggior parte dei settori dell’economia.

Lo sviluppo dell’utilizzo dell’AI porta all’adattamento delle tecnologie nei settori classici dell’economia lungo l’intera catena del valore e le trasforma, portando all’algoritizzazione di quasi tutte le funzionalità, dalla logistica alla gestione aziendale.

Utilizzo dell’intelligenza artificiale per la difesa e gli affari militari

Utilizzare nell'istruzione

Usare l’intelligenza artificiale negli affari

L’intelligenza artificiale nella lotta alle frodi

L’11 luglio 2019 è stato reso noto che in soli due anni l’intelligenza artificiale e il machine learning verranno utilizzati per combattere le frodi tre volte più spesso rispetto a luglio 2019. Tali dati sono stati ottenuti durante uno studio congiunto di SAS e dell'Association of Certified Fraud Examiners (ACFE). A luglio 2019, tali strumenti antifrode erano già utilizzati nel 13% delle organizzazioni che hanno preso parte al sondaggio e un altro 25% ha dichiarato di volerli implementare entro uno o due anni. Per saperne di più.

L’intelligenza artificiale nel settore dell’energia elettrica

• A livello di progettazione: migliore previsione della generazione e della domanda di risorse energetiche, valutazione dell'affidabilità delle apparecchiature di generazione di energia, automazione dell'aumento della produzione quando la domanda aumenta.
• A livello di produzione: ottimizzazione della manutenzione preventiva delle apparecchiature, aumento dell'efficienza della generazione, riduzione delle perdite, prevenzione del furto di risorse energetiche.
• A livello di promozione: ottimizzazione dei prezzi in base all'ora del giorno e fatturazione dinamica.
• A livello di fornitura del servizio: selezione automatica del fornitore più redditizio, statistiche dettagliate sui consumi, servizio clienti automatizzato, ottimizzazione del consumo energetico tenendo conto delle abitudini e del comportamento del cliente.

L'intelligenza artificiale nel settore manifatturiero

• A livello di progettazione: aumento dell'efficienza dello sviluppo di nuovi prodotti, valutazione automatizzata dei fornitori e analisi dei requisiti dei pezzi di ricambio.
• A livello di produzione: migliorare il processo di completamento delle attività, automatizzare le catene di montaggio, ridurre il numero di errori, ridurre i tempi di consegna delle materie prime.
• A livello di promozione: previsione del volume dei servizi di supporto e manutenzione, gestione dei prezzi.
• A livello di fornitura del servizio: miglioramento della pianificazione dei percorsi della flotta di veicoli, domanda di risorse della flotta, miglioramento della qualità della formazione dei tecnici dell'assistenza.

L’intelligenza artificiale nelle banche

• Riconoscimento di pattern - usato incl. riconoscere i clienti nelle filiali e proporre loro offerte specializzate.

L'intelligenza artificiale nei trasporti

• L'industria automobilistica è sull'orlo di una rivoluzione: 5 sfide dell'era della guida senza pilota

L'intelligenza artificiale nella logistica

L'intelligenza artificiale nella produzione della birra

L’intelligenza artificiale in magistratura

Gli sviluppi nel campo dell’intelligenza artificiale contribuiranno a cambiare radicalmente il sistema giudiziario, rendendolo più giusto e libero da schemi di corruzione. Questa opinione è stata espressa nell'estate del 2017 da Vladimir Krylov, dottore in scienze tecniche, consulente tecnico di Artezio.

Lo scienziato ritiene che le soluzioni esistenti nel campo dell'intelligenza artificiale possano essere applicate con successo in vari ambiti dell'economia e della vita pubblica. L’esperto sottolinea che l’intelligenza artificiale viene utilizzata con successo in medicina, ma in futuro potrà cambiare completamente il sistema giudiziario.

“Guardando ogni giorno le notizie sugli sviluppi nel campo dell'intelligenza artificiale, rimani solo stupito dall'inesauribile immaginazione e dalla fecondità dei ricercatori e degli sviluppatori in questo campo. I resoconti sulla ricerca scientifica sono costantemente intervallati da pubblicazioni su nuovi prodotti che irrompono sul mercato e resoconti di risultati sorprendenti ottenuti attraverso l’uso dell’intelligenza artificiale in vari campi. Se parliamo di eventi attesi, accompagnati da un notevole clamore mediatico, in cui l'intelligenza artificiale diventerà nuovamente l'eroe delle notizie, probabilmente non rischierò di fare previsioni tecnologiche. Posso presumere che il prossimo evento sarà l'apparizione da qualche parte di un tribunale estremamente competente sotto forma di intelligenza artificiale, giusta e incorruttibile. Ciò avverrà, a quanto pare, nel 2020-2025. E i processi che si svolgeranno in questo tribunale porteranno a riflessioni inaspettate e al desiderio di molte persone di trasferire sull’IA gran parte dei processi di gestione della società umana”.

Lo scienziato riconosce l’uso dell’intelligenza artificiale nel sistema giudiziario come un “passo logico” per sviluppare l’uguaglianza legislativa e la giustizia. L'intelligenza artificiale non è soggetta alla corruzione e alle emozioni, può aderire rigorosamente al quadro legislativo e prendere decisioni tenendo conto di molti fattori, compresi i dati che caratterizzano le parti in causa. Per analogia con il campo medico, i giudici robot possono operare con i big data provenienti dagli archivi dei servizi governativi. Si può presumere che

Musica

Pittura

Nel 2015, il team di Google ha testato le reti neurali per vedere se potevano creare immagini da sole. Quindi l'intelligenza artificiale è stata addestrata utilizzando un gran numero di immagini diverse. Tuttavia, quando alla macchina è stato “chiesto” di rappresentare qualcosa da sola, si è scoperto che interpretava il mondo che ci circondava in un modo un po’ strano. Ad esempio, per il compito di disegnare manubri, gli sviluppatori hanno ricevuto un'immagine in cui il metallo era collegato da mani umane. Ciò è probabilmente dovuto al fatto che durante la fase di allenamento le immagini analizzate con manubri contenevano mani e la rete neurale lo ha interpretato in modo errato.

Il 26 febbraio 2016, durante un'asta speciale a San Francisco, i rappresentanti di Google hanno raccolto circa 98mila dollari da dipinti psichedelici creati dall'intelligenza artificiale, fondi che sono stati donati in beneficenza. Di seguito viene presentata una delle immagini di maggior successo dell'auto.

Un quadro dipinto dall'intelligenza artificiale di Google.

Lo vediamo continuamente. “RESTful” questo, protocollo “REST” quello, ecc. Tuttavia, molti di noi non capiscono esattamente cosa significhi. Risolveremo esattamente questa lacuna in questo articolo!

Stato

Nell’informatica (e nella matematica, in una certa misura), esiste il concetto di stato. Un certo sistema può essere in stato UN oppure può essere nello stato B oppure può essere un insieme di altri stati (di solito, un elenco finito di stati).

Ad esempio, supponiamo che tu scriva un programma che faccia diventare lo schermo rosso se la temperatura è superiore a 80 gradi Fahrenheit o blu se la temperatura è inferiore a 80 gradi Fahrenheit.

Possiamo chiamare il primo stato (temp > 80 gradi) stato “A” e il secondo stato (temp< 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

Questa è l’idea generale di Stato. Ecco la definizione data dall’onnisciente Wikipedia:

“Nell’informatica e nella teoria degli automi, lo stato di un circuito logico digitale o di un programma per computer è un termine tecnico per tutte le informazioni memorizzate, in un dato momento, che vengono utilizzate dal circuito o dal programma.”

Insomma, si tratta di una sorta di “combinazione” di tutte le informazioni di cui il programma tiene conto.

Ora faremo un salto in qualcosa che è considerato in gran parte teorico e inutile e poi ci collegheremo in qualche modo al mondo molto pratico di REST.

Macchine di Turing

C'era quest'uomo di nome Alan Turing, ed era un matematico piuttosto intelligente con un interesse per il funzionamento dei computer. Concepì un computer immaginario (che, come vedremo, è in realtà impossibile da costruire) con il quale ragionava su cose che accadono nei computer reali.

Il computer è costituito da un nastro di lunghezza infinita, con una testina attraverso la quale passa il nastro. Il nastro ha delle “celle” sulle quali è possibile scrivere informazioni (numeri, colori, ecc.). Il nastro si muove attraverso questa macchina, a destra o a sinistra, una cella alla volta. La macchina esegue la scansione di ciò che è già presente sul nastro e, a seconda dello stato in cui si trova, riscrive qualcosa sul nastro e, successivamente, modifica il suo stato.

Potresti voler leggere di nuovo quella definizione per assimilarla completamente. L'essenza dell'idea è che esegue operazioni sulla memoria in base allo stato e modifica gli stati in base alle operazioni sulla memoria.

Sembra una fantasia teorica abbastanza inutile (anche se non c'è assolutamente nulla di sbagliato in questo, leggi l'Apologia di un matematico se ti stai chiedendo perché le persone si interessano a cose teoriche). Tuttavia, è probabilmente il concetto più fondamentale dell’informatica.

Utilizzando la macchina di Turing, gli informatici sono in grado di ragionare su qualsiasi algoritmo che possa essere eseguito su un computer. In effetti, la macchina di Turing ha portato a molti progressi nell’informatica.

Quindi, la Macchina di Turing ci mostra che oggi (nota: non sto considerando i processori di riduzione del grafico), letteralmente tutto nell’informatica si basa sull’idea di stato.

Il network

Poi è arrivato il concetto di Internet. Questo è un luogo in cui i pacchetti possono andare in tilt e vengono rispediti finché non raggiungono la loro destinazione. In generale non avviene mai una trasmissione completa dei dati completi.

I clienti entrano velocemente e se ne vanno due volte più velocemente. Pertanto, mantenere lo stato client non ha molto senso quando si lavora su un sistema di rete.

Inoltre, in generale, mantenere uno stato eccessivo in un sistema è stato motivo di grave sofferenza (il che porta anche a linguaggi di programmazione funzionali, che non consentono il mantenimento dello stato in gran parte del codice).

Ora, le persone avevano bisogno di un protocollo di rete per Internet che fosse semplice, veloce e gestisse bene la gestione dello stato in un ambiente estremamente dinamico.

Quel protocollo era HTTP e la teoria nata dal lavoro su HTTP fu etichettata REST.

RIPOSO

REST sta per: Trasferimento di Stato REpresentazionale. È un sistema costruito attorno al concetto “client-server” su cui sono costruite le reti (beh, ci sono anche reti di tipo peer to peer, ma client-sever è probabilmente l’architettura più semplice e testata). Il nome stesso è leggermente fuorviante, poiché il server è completamente privo di stato!

Ci sono alcuni vincoli che tutti i sistemi che dichiarano di essere “RESTful” devono seguire.

Prima di tutto, esso dovere essere un sistema client-server. Questo vincolo è stato modificato in passato, ma nella definizione formale (e, affinché la teoria REST funzioni correttamente), abbiamo server a cui i client possono connettersi.

Il server è completamente senza stato. Ciò significa che per ogni richiesta del client al server, sul server non viene riservato nessuno stato. Ad esempio, se un client (utilizzando HTTP), richiede la pagina indice e successivamente richiede la pagina /utente/home, le due richieste sono completamente indipendenti l'una dall'altra. Il cliente tiene Tutto dello stato del sistema (quindi abbiamo il pulsante Indietro).

Le risposte dal server devono essere memorizzabili nella cache, il che significa che deve esserci un sistema sul server che identifichi le risposte come memorizzabili nella cache o meno, in modo che i client (ad esempio i browser Web) possano trarre vantaggio dalla cache.

Infine, dobbiamo avere un'interfaccia semplice, pulita e uniforme. Se hai avuto esperienza con il funzionamento di HTTP, i moduli di richiesta sono molto semplici. Sono in gran parte verbi e sostantivi con un formato molto facile da analizzare e leggibile dall'uomo. SOAP è un'altra forma di protocollo di rete che annulla completamente questo requisito e, pertanto, è spesso molto difficile lavorarci.

Ora, cosa comportano tutte queste proprietà, se messe insieme?

Implicazioni del REST

Ci consentono di creare sistemi nettamente separati, scalabili e facilmente debuggabili.

Consideriamo innanzitutto la limitazione dell'apolidia sul server, potrebbe essere il bit più importante (e, anche, più spesso violato dalle cosiddette architetture RESTful).

Come accennato in precedenza, in un'architettura client-server i client sono molto agili; attivano le richieste e improvvisamente interrompono tutte le comunicazioni. In questo tipo di situazione, è molto più pulito non salvare lo stato del client sul server. Questo ci permette di ragionare molto facilmente sui server HTTP; ogni richiesta del cliente può essere trattata come se fosse un cliente completamente nuovo e non farebbe un centesimo di differenza.

In secondo luogo, le risposte memorizzabili nella cache significano che i client sono in grado di ottenere i dati molto più velocemente, perché spesso i dati possono essere recuperati dalla memoria del client. Ciò aumenta immediatamente le prestazioni del client e, in alcuni sistemi, la scalabilità del server.

L'interfaccia uniforme potrebbe essere proprio la più importante. Avendo lavorato con SOAP, posso dirti che il formato semplice di HTTP è una benedizione quando si tenta di eseguire il debug del codice del server e lo stesso vale per altri sistemi RESTful.

Progettare un sistema RESTful

Diciamo che dobbiamo scrivere un server che restituisca le quotazioni azionarie, oltre a conservare un elenco di quotazioni azionarie da monitorare (e l'utente può aggiungere o cancellare l'elenco).

Questo è un caso eccellente per un sistema RESTful, perché è intrinsecamente indipendente dall'identità del client. Pertanto, non è necessario che il server conservi alcuno stato relativo al client.

Iniziamo innanzitutto definendo come funzionerà il linguaggio del protocollo (un po’ come i verbi GET e POST di HTTP):

RICEVI UN PREVENTIVO ticker- Fornisce il prezzo per un particolare titolo
AGGIUNTA ticker- aggiunge il titolo indicato all'elenco
GETLIST: ottiene un elenco di azioni nell'elenco separato da virgole

È un protocollo abbastanza semplice e non mantiene alcuno stato sul server. Ora, per quanto riguarda il caching, possiamo dire che aggiorniamo i prezzi ogni ora, quindi le cache vecchie di più di un'ora potrebbero essere buttate via.

E questo è tutto! Naturalmente dobbiamo ancora implementarlo, ma l'idea generale del sistema è abbastanza semplice e pulita!

Conclusione

Si spera che questo articolo ti abbia fornito una solida conoscenza di REST.

Inoltre, spero che ora sarai in grado di denunciare le persone che usano troppo il termine "RESTful" - posso dirti che ce ne sono molti!

TURING

TURING(Turing) Alan (1912-54), matematico e logico inglese che formulò teorie che in seguito divennero la base della tecnologia informatica. Nel 1937 inventò Macchina di Turing - un'ipotetica macchina in grado di trasformare un insieme di comandi in input. È stato il precursore dei computer moderni. Turing utilizzò l'idea del computer anche per fornire una dimostrazione alternativa e più semplice del teorema di incompletezza di Gödel. Turing ha svolto un ruolo importante nella risoluzione di Enigma, un complesso metodo di crittografia utilizzato dalla Germania durante la seconda guerra mondiale. Nel 1948 partecipò alla creazione di uno dei primi computer al mondo. Nel 1950 inventò Test di Turing - doveva essere un test sulla capacità di un computer di "pensare". In sostanza si affermava che una persona non sarebbe in grado di distinguere un dialogo con una macchina da un dialogo con un'altra persona. Questo lavoro ha aperto la strada alla creazione dell’INTELLIGENZA ARTIFICIALE. Turing si occupò anche di biologia teorica. In corso "Basi chimiche della morfogenesi"(1952) propose un modello che descrive l'origine dei vari modelli strutturali degli organismi in biologia. Da allora, tali modelli sono stati spesso utilizzati per descrivere e spiegare molti sistemi osservati in natura. Turing si suicidò dopo essere stato ufficialmente accusato di omosessualità.

Dizionario enciclopedico scientifico e tecnico.

Scopri cos'è "TURING" in altri dizionari:

Turing, Alan Mathison Alan Turing Alan Mathison Turing Monumento a Sackville Park Data di nascita ... Wikipedia

- (Turing) Alan Mathieson (1912-54), matematico inglese. Nel 1936-1937 introdusse il concetto matematico di un equivalente astratto di un algoritmo, o di una funzione calcolabile, che allora venne chiamata macchina di Turing... Enciclopedia moderna

- (Turing), Alan Matheson (23 giugno 1912-7 giugno 1954) - inglese. logico e matematico. Nel 1936-1937 propose un modello di calcolo idealizzato della macchina. processo - uno schema computazionale vicino alle azioni della persona che esegue i calcoli e proposto... ... Enciclopedia filosofica

Turing A.- Turing A. Matematico inglese. Argomenti sicurezza informatica IT Turing… Guida del traduttore tecnico

Alan Turing Alan Turing Monumento a Sackville Park Data di nascita: 23 giugno 1912 Luogo di nascita: Londra, Inghilterra Data di morte: 7 giugno 1954 ... Wikipedia

Turing- Il matematico inglese Alan M. Turing, uno dei creatori dei fondamenti logici della tecnologia informatica, in particolare, ha fornito una delle definizioni formali dell'algoritmo; ha dimostrato che esiste una classe di computer in grado di simulare... ... Il mondo di Lem - Dizionario e guida

- (Turing) Alan Mathieson (23.6.1912, Londra, 7.6.1954, Wilmslow, vicino Manchester), matematico inglese. Membro della Royal Society (1951). Dopo la laurea all'Università di Cambridge (1935), lavorò alla sua tesi di dottorato a Princeton... ... Grande Enciclopedia Sovietica

Turing A.M.- TURING (Turing) Alan Mathieson (191254), inglese. matematico. Di base tr. in matematica logica, calcola. matematica. Nel 193637 introdusse la matematica. il concetto di equivalente astratto di un algoritmo, o di una funzione calcolabile, allora chiamata. macchina T... Dizionario biografico

- (full Alan Mathison Turing) (23 giugno 1912, Londra 7 giugno 1954, Wilmslow, UK), matematico britannico, autore di lavori sulla logica matematica e sulla matematica computazionale. Nel 1936-1937 introdusse il concetto matematico... Dizionario enciclopedico

Libri

• Può una macchina pensare? Teoria generale e logica degli automi. Numero 14, Turing A., Questo libro, contenente le opere di Alan Turing e John von Neumann, che furono all'origine della creazione dei primi computer pensanti, appartiene ai classici della filosofia filosofico-cibernetica... Categoria: banche dati Serie: Scienze artificiali Editore: URSS, Produttore: URSS,
• Può una macchina pensare? Teoria generale e logica degli automi. Numero 14, Turing A., Questo libro, contenente le opere di Alan Turing e John von Neumann, che furono all'origine della creazione delle prime “macchine pensanti” dei computer, appartiene ai classici della filosofia filosofico-cibernetica direzione... Categoria: