Chi, dopo aver preso in prestito l'idea da Emil Post, se l'è inventata, si crede, nel 1936. Nonostante la definizione formale piuttosto complicata, l'idea è semplice in linea di principio. Per capirlo, facciamo una passeggiata tra le pagine di Wikipedia.
Prima di tutto, arriviamo alla pagina, che, appunto, si chiama “Macchina di Turing”.
Macchina di Turing
Macchina di Turing (MT)- un'astrazione matematica che rappresenta un tipo generale di computer. È stato proposto da Alan Turing nell'anno di formalizzare il concetto di algoritmo.
La macchina di Turing è un'estensione del modello dell'automa finito e, secondo la tesi di Church-Turing, è in grado di imitare (se esiste un programma appropriato) qualsiasi macchina la cui azione è quella di spostarsi da uno stato discreto all'altro.
La composizione della Turing Machine include infinite in entrambe le direzioni nastro, diviso in celle, e dispositivo di controllo con un numero finito di stati.
Il dispositivo di controllo può spostarsi a sinistra ea destra lungo il nastro, leggere e scrivere caratteri di un alfabeto finito nelle celle. Uno speciale vuoto un simbolo che riempie tutte le celle del nastro, tranne quelle di esse (un numero finito) su cui sono registrati i dati in ingresso.
Il dispositivo di controllo contiene saltare il tavolo, che rappresenta l'algoritmo, realizzabile data Macchina di Turing. Ciascuna regola della tabella indica alla macchina, a seconda dello stato corrente e del simbolo osservato nella cella corrente, di scrivere un nuovo simbolo in questa cella, passare a un nuovo stato e spostare una cella a sinistra oa destra. Alcuni stati della Turing Machine possono essere etichettati come terminale e il passaggio a uno qualsiasi di essi significa la fine del lavoro, l'arresto dell'algoritmo.
Viene chiamata la macchina di Turing deterministico se ciascuna combinazione di stato e simbolo della barra multifunzione nella tabella corrisponde al massimo a una regola, e non deterministico altrimenti.
Quindi, la macchina di Turing è un'astrazione matematica, una costruzione speculativa della mente umana: non esiste in natura. O c'è? Viene subito in mente come funziona una cellula vivente. Almeno due esempi.
1. Per la produzione di proteine in una cellula con l'aiuto di un enzima complesso - l'RNA polimerasi - le informazioni vengono lette dal DNA, una sorta di nastro informativo della macchina di Turing. Qui, tuttavia, le cellule del nastro stesso non vengono sovrascritte, ma per il resto il processo è molto simile: l'RNA polimerasi si trova sul DNA e si muove lungo di esso in una direzione, mentre sintetizza un filamento di RNA, un acido nucleico simile al DNA. L'RNA finito, staccandosi dall'enzima, trasporta informazioni agli organelli cellulari in cui vengono prodotte le proteine.
2. Il processo di correzione degli errori nel DNA è ancora più simile alla macchina di Turing: la sua riparazione. Qui, la DNA polimerasi, insieme ad altre proteine, si muove lungo il nastro del DNA e ne legge entrambe le metà (il DNA genomico, come sapete, è costituito da due filamenti intrecciati che trasportano le stesse informazioni). Se le informazioni nelle metà non corrispondono, la DNA polimerasi prende una di esse come modello e "regola" l'altra.
Tale analogia non è nuova e su Wikipedia è anche descritta nell'articolo "Computer molecolare":
calcolatore molecolare
Calcolo biomolecolare o computer molecolari o anche DNA - o RNA - informatica - tutti questi termini sono apparsi all'incrocio di scienze così diverse come la genetica molecolare e la tecnologia informatica.
Il calcolo biomolecolare è un nome collettivo per varie tecniche legate in un modo o nell'altro al DNA o all'RNA. Nei calcoli del DNA, i dati non sono presentati sotto forma di zeri e uno, ma sotto forma di una struttura molecolare costruita sulla base dell'elica del DNA. Il ruolo del software per la lettura, la copia e la gestione dei dati è svolto da speciali enzimi.
La base dell'intero sistema di archiviazione delle informazioni biologiche, e quindi dei computer del DNA, è la capacità degli atomi di idrogeno, che fanno parte dei composti azotati (adenina, timina, citosina e guanina), in determinate condizioni, di essere attratti l'uno dall'altro, formando coppie legate non valenti. D'altra parte, queste sostanze possono legarsi valentemente a combinazioni di una molecola di zucchero (desossiribosio) e fosfato, formando i cosiddetti nucleotidi. I nucleotidi, a loro volta, formano facilmente polimeri lunghi decine di milioni di basi. In queste supermolecole, fosfato e desossiribosio svolgono il ruolo di struttura portante (si alternano nella catena), mentre i composti azotati codificano informazioni.
La molecola risulta essere diretta: inizia con un gruppo fosfato e termina con il desossiribosio. I filamenti lunghi di DNA sono chiamati filamenti, quelli corti sono chiamati oligonucleotidi. Ogni molecola di DNA corrisponde a un altro DNA, il cosiddetto complemento Watson-Crick. Ha la direzione opposta rispetto alla molecola originale. Come risultato dell'attrazione dell'adenina sulla timina e della citosina sulla guanina, si forma la famosa doppia elica, che consente la duplicazione del DNA durante la riproduzione cellulare. Il compito del raddoppio viene risolto con l'aiuto di uno speciale enzima proteico: la polimerasi. La sintesi inizia solo se un pezzo del suo complemento è attaccato al DNA.Questa proprietà è utilizzata attivamente nella biologia molecolare e nell'informatica molecolare. Al centro, la DNA + polimerasi è un'implementazione di una macchina di Turing, composta da due nastri e un pannello di controllo programmabile. Il telecomando legge i dati da un nastro, li elabora secondo un algoritmo e li scrive su un altro nastro. La polimerasi legge anche in sequenza i dati iniziali da un nastro (DNA) e sulla loro base forma un nastro, per così dire, con i risultati dei calcoli (addizione di Watson-Crick).
Prospettive leggermente fantastiche alimentano solo la nostra curiosità. Nel frattempo, non abbiamo ancora capito tutto sulla macchina di Turing. Come ricorderete, nell'articolo di Wikipedia è stato chiamato un'estensione della macchina a stati. Che cos'è una macchina a stati finiti? Per fortuna c'è un link ad esso. Percorrendolo, apprendiamo che:
macchina a stati
Gli automi astratti costituiscono una classe fondamentale di modelli discreti sia come modello a sé stante, sia come componente principale di macchine di Turing, automi push-down, automi finiti e altri convertitori di informazioni.
Con ogni definizione, ci intromettiamo sempre di più nel regno della matematica pura. Il linguaggio diventa più rigoroso, compaiono definizioni formali, costituite da simboli matematici. Se andiamo oltre, arriveremo alla teoria degli algoritmi e alla teoria della computabilità. Puoi viaggiare a lungo tra le pagine di Wikipedia, ma è meglio fare scorta di acqua e cibo nel caso ti aggiri nel deserto degli assiomi e delle definizioni, o almeno link affidabili a libri di testo di matematica, ad esempio http: //www.mccme.ru/free-books/, o articoli della rivista "Potential";)
Si spera che, dopo questa spiegazione, ti sia diventato un po' più chiaro cos'è esattamente una macchina di Turing?
Torniamo alla storia di questo termine.
Quindi, come abbiamo già detto, Alan Turing parlò al mondo della sua macchina nel 1937 nella cosiddetta Church-Turing Thesis. A proposito di Alan Turing - il primo hacker e pioniere dell'informatica, come è scritto sulla targa commemorativa dell'hotel in cui è nato, l'articolo "Alan Turing" ci dirà. Non daremo qui il testo completo dell'articolo, ma di per sé non è molto dettagliato.
Alan Turing
Turing, Alan Mathison(23 giugno 1912 - 7 giugno 1954) - Matematico inglese, logico, crittografo, inventore della Macchina di Turing.
L'articolo stesso è più sul lavoro di Turing: oltre al testo sulla macchina di Turing, che daremo più avanti, si dice che ha lavorato sul "problema sospeso" (Divertente, vero? Non c'erano ancora i computer , e anche Windows, ma c'era già un problema di blocco.); l'eroica storia di come Turing ha decifrato il codice Enigma durante la seconda guerra mondiale e quindi ha salvato il Regno Unito; il fatto che sia il fondatore della teoria dell'intelligenza artificiale, nonché la menzione del famoso test di Turing. Ora questo test non è più usato spesso come inizio di una storia di fantascienza, ma il problema dell'umano nella macchina rimarrà sempre un classico, come i romanzi di Isaac Asimov e Stanislav Lem.
Nonostante sia antiquato, il test di Turing è riemerso in modo inaspettato nel mondo odierno della comunicazione su Internet. Ad esempio, puoi incontrare il testo del dialogo di due utenti ICQ, uno dei quali è un "bot", e il compito è determinare quale. Oppure un utente sconosciuto, forse un robot ICQ, potrebbe bussare alla tua porta. Lo riconosci? Studiando teoria, potresti riuscire ad applicare il test di Turing in tempo e non farti ingannare. Puoi iniziare il tuo studio con il corrispondente articolo di Wikipedia, quindi seguire i collegamenti forniti alla fine dell'articolo:
Prova di Turing
Prova di Turing- un test proposto da Alan Turing nel 1950 nell'articolo "Computing machinery and intelligence" per verificare se un computer è intelligente nel senso umano della parola.
Il giudice (umano) corrisponde in linguaggio naturale a due interlocutori, uno dei quali è umano, l'altro è un computer. Se il giudice non è in grado di determinare in modo affidabile chi è chi, il computer ha superato il test. Si presume che ciascuno degli interlocutori cerchi di essere riconosciuto come persona. Per rendere il test semplice e universale, la corrispondenza è ridotta a messaggi di testo.
La corrispondenza deve avvenire a intervalli controllati in modo che il giudice non possa trarre conclusioni dalla velocità delle risposte. (Al tempo di Turing, i computer reagivano più lentamente degli umani. Ora questa regola è necessaria perché reagiscono molto più velocemente degli umani.)
Il test è stato ispirato da un gioco di società in cui gli ospiti hanno cercato di indovinare il sesso di una persona in un'altra stanza scrivendo domande e leggendo le risposte. Nella formulazione originale di Turing, una persona doveva fingere di essere una persona del sesso opposto e il test è durato 5 minuti. Ora queste regole non sono considerate necessarie e non sono incluse nella specifica del test.
Turing ha proposto un test per sostituire l'insensata, a suo avviso, domanda "può pensare una macchina?" a uno più specifico.
Turing predisse che i computer avrebbero finalmente superato il suo test. Credeva che entro l'anno 2000, un computer con una memoria di 1 miliardo di bit (circa 119 MB) in un test di 5 minuti potesse ingannare i giudici il 30% delle volte. Questa previsione non si è avverata. (Certo, alla prima competizione Loebner, il programma per computer "PC Therapist" sull'IBM PC 386 è riuscito a ingannare 5 giudici su 10, ma non ha contato il risultato e nel 1994 la competizione è stata resa più difficile.) Turing prevedeva anche che la combinazione "macchina pensante" non sarebbe stata considerata un ossimoro e che la formazione informatica avrebbe svolto un ruolo importante nella costruzione di computer potenti (con cui la maggior parte dei ricercatori moderni concorda).
Finora, nessun programma si è nemmeno avvicinato al superamento del test. Programmi come ELIZA a volte facevano credere alle persone di parlare con una persona, come in un esperimento informale chiamato AOLiza. Ma tali "successi" non stanno superando il test di Turing. In primo luogo, la persona in tali conversazioni non aveva motivo di credere che stesse parlando al programma, mentre nel vero test di Turing la persona sta attivamente cercando di determinare con chi sta parlando. In secondo luogo, i casi documentati si trovano solitamente in chat room come IRC, dove molte delle conversazioni sono imprecise e senza senso. Terzo, molti utenti di IRC usano l'inglese come seconda o terza lingua ed è probabile che la risposta senza senso del programma sia attribuita alla barriera linguistica. In quarto luogo, molti utenti non sanno nulla di Elise e di programmi simili e non possono riconoscere gli errori completamente inumani che questi programmi fanno.
Ogni anno c'è una competizione tra programmi parlanti e il più umano, secondo i giudici, riceve il premio Loebner. C'è un premio aggiuntivo per un programma che secondo i giudici supererà il test di Turing. Questo premio non è stato ancora assegnato.
Il miglior risultato nella prova di Turing è stato mostrato dal programma A.L.I.C.E. aver vinto la prova 3 volte (nel 2000, 2001 e 2004).
Collegamenti
- Turing A. M. Macchine informatiche e mente. // In: Hofstader D., Dennett D. L'occhio della mente. - Samara: Bahrakh-M, 2003. - S. 47-59.
- Libro in inglese: Roger Penrose "The Emperor's New Mind".
- Articolo di Alan Turing:
- Alan Turing, Macchine informatiche e intelligenza, Mente, vol. LIX, no. 236, ottobre 1950, pp. 433-460.
- In linea:
- Articolo di G. Oppy e D. Dowe sul test di Turing dalla Stanford Encyclopedia of Philosophy (in inglese)
- "Test di Turing: 50 anni dopo" una rassegna di 50 anni di lavoro sul test di Turing, dal punto di vista del 2000 (in inglese).
Torniamo di nuovo alla macchina di Turing. In un estratto da un articolo su Alan Turing, si afferma che per la prima volta il concetto di macchina di Turing è stato proposto nell'ambito della cosiddetta. Tesi di Church-Turing:
Estratto dall'articolo di Wikipedia "Alan Turing"
Qualsiasi funzione calcolabile intuitivamente è parzialmente calcolabile o, equivalentemente, può essere calcolata da qualche macchina di Turing.
Alan Turing ha suggerito (noto come Church-Turing Thesis) che qualsiasi algoritmo nel senso intuitivo della parola può essere rappresentato da una macchina di Turing equivalente. L'affinamento del concetto di computabilità basato sul concetto di macchina di Turing (e altri concetti ad esso equivalenti) ha aperto opportunità per la prova rigorosa dell'irrisolvibilità algoritmica di vari problemi di massa (cioè problemi di trovare un metodo unificato per risolvere un determinato classe di problemi, le cui condizioni possono variare entro certi limiti). L'esempio più semplice di un problema di massa algoritmicamente indecidibile è il cosiddetto problema di applicabilità dell'algoritmo (chiamato anche problema di arresto). Consiste in quanto segue: è necessario trovare un metodo generale che consenta, per una macchina di Turing arbitraria (data dal suo programma) e uno stato iniziale arbitrario del nastro di questa macchina, di determinare se il funzionamento della macchina termina in un numero finito di passaggi, o se continuerà indefinitamente.
In un articolo intitolato "The Church-Turing Thesis" scrivono di lui in questo modo:
Tesi di Church-Turing
Tesi di Church-Turing- un'affermazione fondamentale per molte aree della scienza, come la teoria della computabilità, l'informatica, la cibernetica teorica, ecc. Questa affermazione è stata fatta da Alonzo Church e Alan Turing a metà degli anni '30.
Nella sua forma più generale, afferma che qualsiasi funzione calcolabile intuitivamente è parzialmente calcolabile o, in modo equivalente, può essere calcolata da qualche macchina di Turing.
La tesi di Church-Turing non può essere rigorosamente provata o smentita, poiché stabilisce una "eguaglianza" tra la nozione rigorosamente formalizzata di una funzione parzialmente calcolabile e la nozione informale di una "funzione intuitivamente calcolabile".
Tesi fisica di Church-Turing si legge: Qualsiasi funzione che può essere calcolata da un dispositivo fisico può essere calcolata da una macchina di Turing.
Da questo bivio ci si può avvicinare, ad esempio, alla teoria della computabilità. Oppure puoi provare a scoprire chi è questa misteriosa Chiesa, con la quale Alan Turing ha avanzato la sua tesi.
Macchina di Turing universale
Macchina di Turing universale chiamata macchina di Turing, che può sostituire qualsiasi macchina di Turing. Dopo aver ricevuto il programma e i dati immessi in input, calcola la risposta che la macchina di Turing, il cui programma è stato fornito in input, calcolerebbe dai dati in input.
Definizione formale
Il programma di qualsiasi macchina di Turing deterministica può essere scritto usando un alfabeto finito composto da simboli di stato, parentesi, frecce e così via; indichiamo questo alfabeto macchina come Σ 1 (\ displaystyle \ Sigma _ (1)). Poi la macchina universale di Turing u per una classe di macchine con un alfabeto Σ 2 (\ displaystyle \ Sigma _ (2)) e K nastri di input è chiamata macchina di Turing con k+1 nastro d'ingresso e alfabeto Σ 1 ∪ Σ 2 (\ displaystyle \ Sigma _ (1) \ tazza \ Sigma _ (2)) tale che se fai domanda per il primo K il valore di input dei nastri e così via k+1è il codice scritto correttamente di alcune macchine di Turing, quindi u darà la stessa risposta che darebbe su questi input M 1 (\ displaystyle M_ (1)), o verrà eseguito a tempo indeterminato se M 1 (\ displaystyle M_ (1)) non fermarti a questi dati.
Il Teorema della Macchina di Turing Universale afferma che tale macchina esiste e modella altre macchine con al massimo una decelerazione quadratica (cioè, se la macchina originale ha prodotto T passi, allora l'universale produrrà al massimo ct2). La dimostrazione di questo teorema è costruttiva (una macchina del genere è facile da costruire, basta descriverla attentamente). Il teorema fu proposto e dimostrato da Turing nel 1936-37.
L'implementazione del software nel linguaggio di programmazione Delphi è abbastanza semplice. Una di queste implementazioni può essere trovata su http://kleron.ucoz.ru/load/24-1-0-52 . È possibile caricare e salvare in un file Excel.
Macchina di Turing non deterministica
Macchina di Turing probabilistica
Una generalizzazione di una macchina di Turing deterministica, in cui, da qualsiasi stato e valore sul nastro, la macchina può effettuare una delle numerose (si può considerare, senza perdita di generalità - due) possibili transizioni e la scelta è fatta in modo probabilistico (lanciando una moneta).
Una macchina di Turing probabilistica è simile a una macchina di Turing non deterministica, solo che invece di una transizione non deterministica, la macchina sceglie una delle opzioni con una certa probabilità.
Esiste anche una definizione alternativa:
Una macchina di Turing probabilistica è una macchina di Turing deterministica che ha inoltre una fonte hardware di bit casuali, un numero qualsiasi dei quali, ad esempio, può "ordinare" e "caricare" su un nastro separato e quindi utilizzare nei calcoli nel solito modo per mt.
La classe di algoritmi che terminano in tempo polinomiale su una macchina di Turing probabilistica e restituiscono una risposta con un errore inferiore a 1/3 è chiamata classe BPP.
Nel 1936 Alan Turing propose di chiarire il concetto di algoritmo esecutore universale astratto. La sua astrattezza sta nel fatto che è un costrutto logico computazionale e non un vero computer. Il termine "esecutore universale" significa che questo esecutore può imitare qualsiasi altro artista. Ad esempio, le operazioni eseguite dai computer reali possono essere simulate su un esecutore universale. Di conseguenza fu chiamata la costruzione computazionale inventata da Turing Macchina di Turing.
Inoltre, si presume che un esecutore universale dovrebbe essere in grado di dimostrare l'esistenza o l'assenza di un algoritmo per una particolare attività.
Cos'è una macchina di Turing?
La macchina di Turing è costituita da un nastro infinito in entrambe le direzioni, diviso in celle, e da un automa (testa), che è controllato dal programma.
I programmi per le macchine di Turing sono scritti sotto forma di tabella, dove la prima colonna e riga contengono le lettere dell'alfabeto esterno e gli eventuali stati interni dell'automa (alfabeto interno). I contenuti della tabella sono istruzioni per la macchina di Turing. La lettera che la testa legge nella cella (su cui si trova attualmente) e lo stato interno della testa determinano quale istruzione eseguire. Il comando è determinato dall'intersezione dei caratteri degli alfabeti esterno e interno nella tabella.
Per specificare una macchina di Turing specifica, è necessario descrivere i seguenti componenti per essa:
- alfabeto esterno. Un insieme finito (ad esempio A), i cui elementi sono chiamati lettere (simboli). Una delle lettere di questo alfabeto (ad esempio uno 0) deve essere un carattere vuoto.
- alfabeto interno. Insieme finito di stati della testa (automa). Uno degli stati (ad esempio, q 1) deve essere iniziale (avvio del programma). Un altro degli stati (q 0) deve essere definitivo (terminando il programma) - lo stato di arresto.
- Salta il tavolo. Descrizione del comportamento dell'automa (testa) in funzione dello stato e del carattere letto.
L'automa di una macchina di Turing nel corso del suo lavoro può eseguire le seguenti azioni:
- Scrivi un carattere dell'alfabeto esterno in una cella (compresa una vuota), sostituendo quella in essa contenuta (compresa una vuota).
- Sposta una cella a sinistra oa destra.
- Cambia il tuo stato interiore.
Un comando per una macchina di Turing è solo una combinazione specifica di questi tre componenti: istruzioni per quale carattere scrivere nella cella (sopra la quale si trova la macchina), dove muoversi e in quale stato andare. Anche se il comando potrebbe non contenere tutti i componenti (ad esempio non modificare il simbolo, non spostarsi o non modificare lo stato interno).
Esempio di macchina di Turing
Diciamo che sul nastro è presente una parola composta dai caratteri #, $, 1 e 0. Vuoi sostituire tutti i caratteri # e $ con zeri. Al momento del lancio, la testa si trova sopra la prima lettera della parola a sinistra. Il programma termina quando la testa è sopra il carattere vuoto dopo la lettera più a destra della parola.
Nota: la lunghezza della parola e la sequenza di caratteri non contano. La figura mostra un esempio della sequenza di esecuzione dei comandi per un caso particolare. Se sul nastro è presente una parola diversa, la sequenza di comandi sarà diversa. Nonostante ciò, questo programma per la macchina di Turing (nella figura - la tabella a sinistra) è applicabile a qualsiasi parola dell'alfabeto esterno descritto (si osserva la proprietà di applicabilità dell'algoritmo a tutti i compiti dello stesso tipo - carattere di massa ).
Puoi complicare il programma. Supponiamo che la testa non si trovi necessariamente sopra la prima, ma sopra qualsiasi carattere della parola. Quindi il programma per una data macchina di Turing potrebbe essere così (o potrebbe essere diverso):
Qui la testa viene spostata a sinistra finché non si trova sopra il carattere vuoto. Successivamente, la macchina entra nello stato q 2 (i cui comandi sono gli stessi dei comandi q 1 del programma precedente).
Ho deciso di spiegare all'umanità il principio dei calcoli algoritmici. Il fatto è che il signor Turing era un profeta dell'era dei computer, quindi semplicemente non poteva fare a meno di dire alla gente cos'è un algoritmo. Così ha inventato una macchina astratta, che ha preso il suo nome. Voglio dire, cognome. Ma facciamolo bene...
L'essenza in parole semplici
Va subito individuato un punto importante: la macchina di Turing è un dispositivo esclusivamente speculativo. Niente di simile esiste in natura. I modelli informatici esistono. Anche quelli attivi. Ma non sono altro che modelli.
Perché? Perché l'argomento della discussione è un nastro senza fine, la cui esistenza fisica a tutti gli effetti in questa fase dello sviluppo della scienza e della tecnologia è possibile solo teoricamente.
Il nastro è costituito da cellule, come una catena di maglie. Le celle contengono dati, come caratteri alfabetici. Bene, o zero e uno. In generale, qualcosa di adatto per l'elaborazione automatica. Questo viene fatto dalla parte mobile della macchina.
Come funziona
La parte mobile è il lettore e lo scrittore. Qualcosa che può leggere il contenuto delle celle, scrivervi qualcosa di proprio e, soprattutto, agire in base ai risultati risultanti.
Inoltre, l'automa può spostare solo una cella alla volta. Destra, sinistra, dove necessario per eseguire calcoli. Ho aggiunto qualcosa qui: devi spostarti per portare via qualcosa. E poi piega di nuovo. E così via per tutto il tempo che desideri, fino al completamento dell'attività. Dopotutto, il nastro è infinito, ci sono abbastanza opzioni per qualsiasi operazione.
In effetti, Alan Turing stava solo cercando di sottolineare che ogni calcolo, non importa quanto complesso possa essere, può essere eseguito per fasi, passo dopo passo, scomponendo il compito in componenti elementari. Questa è l'essenza dell'algoritmo.
Diverse varianti
La cibernetica alle prime armi guardò la macchina di Turing e capì che non c'era nulla di cui lamentarsi. In effetti, i programmi per computer dovrebbero essere costruiti sulla base di algoritmi: l'esecuzione graduale delle istruzioni.
Allo stesso tempo, la gloria di Alan Turing non ha dato tregua a molti e i seguaci hanno iniziato, come si suol dire, a coglierne i riflessi. Cominciarono a inventare macchine di Turing multidimensionali, con molti nastri, "semi-infinite" ecc.
Cercheremo di portare almeno un po' di chiarezza in questo caos e prendere in considerazione le opzioni reali per il dispositivo in discussione.
- non deterministico- questa è una macchina di Turing che agisce sul nastro con le celle sopra descritte in base alla situazione che si presenta in una particolare fase di calcolo. Ovunque vorrà, si trasferirà lì, in altre parole.
- deterministico uno con istruzioni specifiche. Ad esempio, se la cella in cui si trova l'automa in esecuzione contiene la lettera A, allora devi passare a quella successiva, con la lettera B, che tu lo voglia o meno.
- Completare- in grado di calcolare tutto in generale che può essere calcolato con operazioni passo-passo. Può persino simulare una macchina in una macchina, un emulatore che descrive il funzionamento di un altro dispositivo simile con algoritmi.
- universale- capace di tutto ciò che può fare qualsiasi macchina di Turing. In generale, qualsiasi, nemmeno inventato. Ovviamente è completo.
Vantaggi pratici
Naturalmente, un algoritmo è un concetto più complesso del semplice spostamento dell'esecuzione attraverso passaggi in uno spazio unidimensionale. Dopotutto, sono possibili ramificazioni, looping, ritorno indietro, utilizzando subroutine.
Inoltre, è impossibile in pratica simulare un numero infinito di celle contenenti dati, se non altro perché le capacità delle apparecchiature informatiche sono limitate.
Tuttavia, esistono programmi di simulazione della macchina di Turing progettati per insegnare agli studenti. I programmatori inesperti sono incoraggiati a sviluppare algoritmi diversi, ad esempio cercare, modificare, aggiungere, riordinare le lettere nelle celle.
Pertanto, i vantaggi della macchina di Turing sono esattamente ciò che il suo creatore, il profeta dell'era dei computer, intendeva: una chiara dimostrazione dell'essenza del calcolo algoritmico.
Pubblicazioni precedenti:
Ultima modifica: 01-04-2013 10:58:05
Etichette materiale: ,
Una macchina di Turing è una raccolta dei seguenti oggetti
- 1) alfabeto esterno A=(a 0 , a 1 , …, a n );
- 2) alfabeto interno Q=(q 1 , q 2 ,…, q m ) - insieme di stati;
- 3) set di caratteri di controllo (P, L, S)
- 4) un nastro infinito in entrambe le direzioni, diviso in celle, in ciascuna delle quali è possibile scrivere un solo carattere dell'alfabeto A in qualsiasi momento discreto;
- 5) un dispositivo di controllo in grado di trovarsi in uno dei tanti stati
Il simbolo di una cella vuota è la lettera dell'alfabeto esterno, uno 0 .
Tra gli stati si distingue l'iniziale q 1, in cui la macchina inizia a lavorare, e lo stato finale (o di arresto) q 0, una volta in cui la macchina si ferma.
Il dispositivo di controllo può spostarsi a sinistra e a destra sul nastro, leggere e scrivere nelle celle del nastro lettere dell'alfabeto A. Il dispositivo di controllo opera secondo comandi che hanno la forma seguente
q io a j > a p X q k
La voce significa quanto segue: se il dispositivo di controllo è nello stato qi e la lettera aj è scritta nella cella visualizzata, allora (1) nella cella viene scritto ap invece di aj , (2) la macchina procede alla visualizzazione la cella successiva a destra da quella appena visualizzata, se X=P, oppure per visualizzare la cella successiva a sinistra, se X=L, oppure continuare a visualizzare la stessa cella nastro, se X=C, (3) il dispositivo di controllo entra nello stato q k.
Poiché il funzionamento della macchina, per condizione, è completamente determinato dal suo stato q, in un dato momento, e dal contenuto a della cella che si sta visualizzando in quel momento, esiste esattamente una regola per ogni possibile configurazione q i a j. Non ci sono regole solo per lo stato finale, in cui la macchina si ferma. Pertanto, il programma macchina di Turing con alfabeto esterno A=(a0, a1, …, an) e alfabeto interno Q=(q1, q2,…, qm) contiene non più di m (n+ 1) istruzioni.
Una parola nell'alfabeto A o nell'alfabeto Q o nell'alfabeto A Q è qualsiasi sequenza di lettere dell'alfabeto corrispondente. Con la configurazione k-esima si intende l'immagine del nastro della macchina con le informazioni che si sono sviluppate su di essa all'inizio del k-esimo passaggio (o la parola dell'alfabeto A scritta sul nastro all'inizio di il k-esimo passaggio), indicando quale cella viene visualizzata in questo passaggio E in che condizioni si trova l'auto? Hanno senso solo le configurazioni finite, ad es. quelli in cui tutte le celle del nastro, con la possibile eccezione di un numero finito, sono vuote. Una configurazione si dice definitiva se lo stato in cui si trova la macchina è definitivo.
Se si sceglie una configurazione non finale della macchina di Turing come quella iniziale, allora il compito della macchina è di trasformare in sequenza (passo dopo passo) la configurazione iniziale secondo il programma della macchina fino al raggiungimento della configurazione finale. Successivamente, il lavoro della macchina di Turing si considera completato e il risultato del lavoro è la configurazione finale raggiunta.
Diremo che una parola b non vuota dell'alfabeto A (à 0 ) = (a 1 , ..., an ) è percepita dalla macchina in una posizione standard se è scritta in celle successive del nastro, tutte le altre celle sono vuote e la macchina esegue la scansione della cella più a sinistra o più a destra tra quelle in cui è scritta la parola b. La posizione standard è detta iniziale (finale) se la macchina che percepisce la parola nella posizione standard è nello stato iniziale q 1 (rispettivamente nello stato di arresto q 0).
Se l'elaborazione della parola b porta la macchina di Turing al suo stato finale, allora si dice che si applica a b, altrimenti non si applica a b (la macchina funziona all'infinito)
Considera un esempio:
Data una macchina di Turing con un alfabeto esterno A \u003d (0, 1) (qui 0 è il simbolo di una cella vuota), un alfabeto di stati interni Q \u003d (q 0, q 1, q 2 ) e con quanto segue diagramma funzionale (programma):
q 1 0 > 1 L q 2 ;
q 1 1 > 0 С q 2 ;
q 2 0 > 0 П q 0 ;
q 2 1 > 1 C q 1;
Questo programma può essere scritto usando la tabella
Al primo passo, il comando opera: q 1 0 > 1 Û q 2 (il dispositivo di controllo è nello stato q1 e nella cella monitorata viene scritta la lettera 0, nella cella viene scritto 1 invece di 0, la testa viene spostato a sinistra, il dispositivo di controllo passa allo stato q2), in Di conseguenza, sulla macchina viene creata la seguente configurazione:
Infine, dopo aver eseguito il comando q 2 0 > 0 P q 0, viene creata una configurazione
Questa configurazione è definitiva perché la macchina è in uno stato di arresto q 0 .
Pertanto, la parola originale 110 viene elaborata dalla macchina nella parola 101.
La sequenza di configurazioni risultante può essere scritta in modo più breve (i contenuti della cella monitorata vengono scritti a destra dello stato in cui si trova attualmente la macchina):
11q 1 0 => 1q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1
La macchina di Turing non è altro che una regola (algoritmo) per convertire parole dell'alfabeto AQ, cioè configurazioni. Quindi, per definire una macchina di Turing, è necessario specificarne gli alfabeti esterni ed interni, il programma, e indicare quale dei simboli denota una cella vuota e lo stato finale.
trascrizione
1 Università statale di Mosca Lomonosov MV Lomonosov Facoltà di matematica computazionale e cibernetica V.N. Pilshchikov, V.G. Abramov, AA Vylitok, IV Macchina di Turing a caldo e algoritmi di Markov. Risoluzione dei problemi (Manuale educativo) Mosca, 2006
2 UDC BBK P32 Pilshchikov V.N., Abramov V.G., Vylitok A.A., Hot I.V. Algoritmi della macchina di Turing e di Markov. Risoluzione dei problemi. (Manuale didattico) - M.: Università statale di Mosca, p. Il Dipartimento Editoria della Facoltà di CMC MSU (licenza LR da) Il manuale è dedicato alla risoluzione di problemi sul tema "Introduzione alla teoria degli algoritmi", studiato al primo anno della Facoltà di CMC MSU nell'ambito della disciplina "Algoritmi e linguaggi algoritmici". Questi sono compiti per la compilazione di algoritmi sotto forma di una macchina di Turing e normali algoritmi di Markov, nonché compiti di natura teorica. Il manuale fornisce le informazioni necessarie sulla teoria degli algoritmi, spiega in dettaglio le tecniche tipiche per la risoluzione dei problemi e offre un ampio insieme di problemi per una soluzione indipendente. Il manuale è progettato per gli studenti del primo anno della facoltà della CMC dell'Università statale di Mosca e per gli insegnanti che conducono seminari sulla programmazione. Revisori: Professore Associato Baula V.G. Professore Associato Korukhova L.S. Pubblicato per decisione del Consiglio editoriale ed editoriale della Facoltà di matematica computazionale e cibernetica dell'Università statale di Mosca. MV Lomonosov. ISBN??? Dipartimento editoriale della Facoltà di matematica computazionale e cibernetica, Università statale di Mosca Lomonosov MV Lomonosov,
3 1. Macchina di Turing Questa sezione tratta i problemi di compilazione di algoritmi per una macchina di Turing. Viene fornita una breve descrizione di questa macchina, vengono spiegati i metodi principali per la compilazione di tali algoritmi con esempi e vengono proposti problemi per una soluzione indipendente. 1.1 Breve descrizione della macchina di Turing Struttura della macchina di Turing La macchina di Turing (MT) è composta da due parti di un nastro e un automa (vedi a sinistra): nastro: abb Λ Λ abb Λ Λ automa: qq Il nastro viene utilizzato per memorizzare informazione. È infinito in entrambe le direzioni ed è diviso in celle che non sono numerate o denominate in alcun modo. Ogni cella può contenere un carattere o niente. Il contenuto della cella può cambiare in essa, puoi scrivere un altro carattere o cancellare il carattere che si trova lì. Accettiamo di chiamare il contenuto vuoto della cella il simbolo "vuoto" e denotiamo il segno Λ ("lambda"). Pertanto, l'immagine del nastro mostrata nella figura a destra è la stessa mostrata nella figura a sinistra. Questa convenzione è conveniente in quanto l'operazione di eliminazione di un carattere in una determinata cella può essere considerata come la scrittura del carattere Λ in questa cella, quindi al posto della lunga frase "scrivi un carattere in una cella o cancella un carattere che si trova lì", tu può semplicemente dire "scrivi un carattere in una cella". La macchina è la parte attiva della MT. In ogni momento, viene posto sotto una delle celle del nastro e ne vede il contenuto; questa è una cella visibile e il simbolo in essa contenuto è un simbolo visibile; il contenuto delle celle vicine e di altre celle non è visibile alla macchina. Inoltre, in ogni momento l'automa si trova in uno degli stati, che sarà indicato dalla lettera q con i numeri: q1, q2, ecc. Trovandosi in un certo stato, l'automa esegue alcune operazioni specifiche (ad esempio, si sposta a destra lungo il nastro, sostituendo tutti i caratteri b con a), mentre si trova in un altro stato, un'altra operazione. Una coppia di un simbolo visibile (S) e lo stato attuale dell'automa (q) sarà chiamata configurazione e denotata
4 Ciclo macchina di Turing L'MT lavora in cicli che vengono eseguiti uno dopo l'altro. Ad ogni ciclo, l'automa MT compie le seguenti tre azioni, e necessariamente nell'ordine indicato: 1) scrive un simbolo S in una cella visibile (in particolare si può scrivere lo stesso simbolo com'era in essa, quindi il contenuto di questa cella non cambia); 2) si sposta di una cella a sinistra (notazione L, da sinistra), o di una cella a destra (notazione R, da destra), o rimane immobile (notazione N). 3) va in uno stato q (in particolare può rimanere nello stesso stato). Formalmente, le azioni di una misura saranno scritte come una tripla: S, , q dove la costruzione tra parentesi quadre indica la possibilità di scrivere una qualsiasi delle lettere L, R o N in questo punto sposta una cella a sinistra e transizione dichiarare q8. Il programma Turing Machine Di per sé, il MT non fa nulla. Per farlo funzionare, devi scrivere un programma per esso. Questo programma è scritto nella forma della tabella seguente: q 1 qjqm S 1 S 2 S i S n Λ S, , q A sinistra sono elencati tutti gli stati in cui può essere l'automa, in alto ci sono tutti i simboli (inclusi Λ) che l'automa può vedere sul nastro. (Quali simboli e stati da indicare nella tabella sono determinati dall'autore del programma.) Alle intersezioni (nelle celle della tabella) sono indicati quei cicli che l'automa deve eseguire quando è nello stato appropriato e vede il simbolo corrispondente sul nastro. In generale, la tabella determina le azioni dell'MT per tutte le possibili configurazioni e quindi imposta completamente il comportamento dell'MT. Descrivere un algoritmo sotto forma di MT significa presentare una tabella del genere. (Nota. Spesso un MT è definito come costituito da un nastro, un automa e un programma, quindi programmi diversi producono MT diversi. Assumeremo, nello spirito dei computer moderni, che esiste un solo MT, ma può eseguire diversi programmi.) 4
5 Regole di esecuzione del programma Prima di eseguire il programma, è necessario eseguire i seguenti passaggi preliminari. Innanzitutto, la parola di input a cui verrà applicato il programma deve essere scritta sul nastro. La parola di input è la sequenza finale di caratteri scritti nelle celle adiacenti del nastro; non ci dovrebbero essere celle vuote all'interno della parola di input e solo le celle vuote dovrebbero essere a sinistra ea destra di essa. Una parola di input vuota significa che tutte le celle del nastro sono vuote. In secondo luogo, è necessario impostare l'automa allo stato q 1 (indicato per primo nella tabella) e posizionarlo sotto il primo simbolo della parola di input: abbq 1 Se la parola di input è vuota, l'automa può guardare qualsiasi cella , perché sono tutti vuoti. Dopo questi passaggi preliminari, inizia l'esecuzione del programma. Nella tabella si trova una cella all'intersezione della prima riga (perché l'automa è nello stato q 1) e la colonna che corrisponde al primo carattere della parola di input (questa non è necessariamente la colonna di sinistra della tabella), e viene eseguito il ciclo indicato in questa cella. Di conseguenza, la macchina sarà in una nuova configurazione. Ora si ripetono le stesse azioni, ma per una nuova configurazione: nella tabella si trova una cella che corrisponde allo stato e al simbolo di questa configurazione e da questa cella viene eseguito un ciclo. Eccetera. Quando termina il programma? Introduciamo il concetto di ciclo di arresto. Questo è un ciclo che non cambia nulla: l'automa scrive nella cella visibile lo stesso simbolo di prima, non si muove e rimane nello stesso stato, cioè questo è il ciclo S,N,q per la configurazione
6 2) Il secondo risultato è “cattivo”: questo è quando la MT va in loop, senza mai arrivare al ciclo di arresto (ad esempio l'automa si sposta a destra ad ogni passo e quindi non può fermarsi, perché il nastro è infinito). In questo caso, si dice che MT non è applicabile alla parola di ingresso data. Non ci può essere alcun dubbio su alcun risultato con un tale risultato. Si noti che lo stesso algoritmo (programma MT) può essere applicabile ad alcune parole di ingresso (ad esempio, stop) e inapplicabile ad altri (ad esempio, loop). Pertanto, l'applicabilità/inapplicabilità dipende non solo dall'algoritmo stesso, ma anche dalla parola di input. A quali parole di input dovrebbe fermarsi l'algoritmo? Su, per così dire, buone parole, cioè su quelli che si riferiscono ai dati iniziali ammissibili del problema da risolvere, per il quale il problema è significativo. Ma qualsiasi parola di input può essere registrata sul nastro, comprese quelle per le quali il compito non ha senso; su tali parole, il comportamento dell'algoritmo non è fisso, può fermarsi (per qualsiasi risultato), oppure può andare in cicli. Convenzioni per abbreviare la registrazione Concordiamo alcune convenzioni che abbreviano la registrazione del programma per MT. 1) Se un simbolo visibile non cambia in una misura, o l'automa non si muove, o lo stato dell'automa non cambia, allora non scriveremo nulla nella posizione corrispondente della misura. Ad esempio, durante la configurazione
7 1.2 Esempi di programmazione MT Diamo un'occhiata agli esempi di programmazione MT per dimostrare alcune tipiche tecniche di programmazione MT. Per abbreviare la formulazione dei problemi, introduciamo le seguenti due convenzioni: indicheremo la parola in ingresso con la lettera P; la lettera A indicherà l'alfabeto della parola in ingresso, ad es. l'insieme di quei simboli di cui e solo in cui P può consistere (si noti, tuttavia, che altri simboli possono comparire nelle parole intermedie e di uscita). Esempio 1 (spostamento dell'automa, sostituzione dei caratteri) A=(0,1,2,3,4,5,6,7,8,9). Sia P una parola non vuota; quindi P è una sequenza di cifre decimali, cioè notazione di un numero intero non negativo nel sistema decimale. È necessario ottenere sul nastro una registrazione di un numero maggiore di 1 rispetto al numero P. Soluzione. Per risolvere questo problema, si propone di eseguire le seguenti azioni: 1. Spostare la macchina sull'ultima cifra del numero. 2. Se questo è un numero compreso tra 0 e 8, sostituirlo con un numero in più 1 e interrompere; ad esempio: se questo è il numero 9, sostituiscilo con 0 e sposta l'automa sulla cifra precedente, quindi aumenta questa penultima cifra di 1 allo stesso modo; es.: Caso speciale: P ha solo nove (es. 99). Quindi l'automa si sposterà a sinistra, sostituendo i nove con zeri, e alla fine si troverà sotto una cella vuota. Scrivi 1 in questa cella vuota e fermati (la risposta sarà 100): Nella forma di un programma per MT, queste azioni sono descritte come segue: Λ q1 0,R,q1 1,R,q1 2,R,q1 3 ,R,q1 4, R,q1 5,R,q1 6,R,q1 7,R,q1 8,R,q1 9,R,q1 Λ,L,q2 q2 1,N,! 2,N! 3,N! 4,N! 5,N! 6,N! 7,N! 8,N! 9,N! 0,L,q2 1,N,! Spiegazioni. q1 è lo stato in cui l'automa "corre" sotto l'ultima cifra del numero. Per fare ciò, si sposta costantemente a destra, senza modificare i numeri visibili e rimanendo nello stesso stato. Ma c'è una caratteristica qui: quando la macchina ha meno di 7
8 è l'ultima cifra, quindi ancora non lo sa (dopotutto, non vede cosa è scritto nelle celle vicine) e lo determinerà solo quando arriva a una cella vuota. Pertanto, raggiunta la prima cella vuota, l'automa torna sotto l'ultima cifra e si porta nello stato q2 (non è più necessario spostarsi a destra). q2 è lo stato in cui l'automa aggiunge 1 alla cifra che vede in quel momento. Innanzitutto è l'ultima cifra del numero; se è compreso tra 0 e 8, la macchina lo sostituisce con una cifra che è 1 in più e si ferma. Ma se questo è il numero 9, l'automa lo sostituisce con 0 e si sposta a sinistra, rimanendo nello stato q2. Pertanto, ora aggiungerà 1 alla cifra precedente. Se anche questa cifra è uguale a 9, l'automa la sostituisce con 0 e si sposta a sinistra, rimanendo nello stato q2 come prima, poiché dovrebbe eseguire la stessa azione aumentare di 1 cifra visibile. Se l'automa si è spostato a sinistra e non c'è alcun numero nella cella visibile (ma c'è "vuoto"), allora scrive 1 qui e si ferma. Si noti che per una parola di input vuota, il nostro problema non è definito, quindi, su questa parola, la MT può comportarsi in qualsiasi modo. Nel nostro programma, ad esempio, con una parola di input vuota, il MT si ferma e dà la risposta 1. Sopra, abbiamo dato il programma in forma completa e non abbreviata. Ora scriviamo il programma in una forma abbreviata, più visiva, mentre a destra diamo una breve spiegazione delle azioni che vengono attuate nei corrispondenti stati dell'automa: Λ q1,r,r,r,r,r,r ,r,r,r,r, l,q2 sotto l'ultima cifra di q2 1,! 2! 3! 4,! 5,! 6! 7! otto,! 9,! 0,L, 1,! numero visibile + 1 Ecco come scriveremo i programmi in futuro. Esempio 2 (analisi dei caratteri) A=(a,b,c). Sposta alla fine il primo carattere di una parola P non vuota. Ad esempio: a b c b b c b a Soluzione. Per risolvere questo problema, si propone di eseguire le seguenti azioni: 1. Ricordare il primo carattere della parola P, quindi cancellare questo carattere. 2. Spostare l'automa a destra sotto la prima cella vuota dopo P e scrivervi il simbolo memorizzato. Come "correre" a destra, lo sappiamo già dall'esempio precedente. Ma come ricordare il primo personaggio? Infatti in MT non c'è nessun altro dispositivo di memorizzazione se non il nastro, ed è inutile memorizzare un simbolo in qualche cella del nastro: non appena l'automa si sposta a sinistra o a destra di questa cella, dimentica immediatamente questo simbolo . Cosa fare? La via d'uscita qui è usare diversi stati dell'automa. Se il primo carattere è a, allora devi andare allo stato q2, in cui l'automa 8
9 corre a destra e scrive a alla fine. Se il simbolo b è stato il primo, allora è necessario passare allo stato q3, dove tutto è fatto allo stesso modo, alla fine viene scritto solo il simbolo b. Se il primo simbolo era c, allora si passa allo stato q4, in cui l'automa aggiunge il simbolo c dopo la parola di input. Pertanto, fissiamo quale fosse il primo simbolo trasferendo l'automa in stati diversi. Questa è una tipica tecnica di programmazione MT. Alla luce di quanto sopra, il programma sarà il seguente: abc Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R, analisi del 1° carattere, rimozione dello stesso, ramificazione q2,r,r ,RA,! registra a a destra q3,r,r,r, b,! registra b a destra q4,r,r,r, c,! scrivi c a destra Considera il comportamento di questo programma su parole di input contenenti al massimo un carattere. Con una parola vuota, che è "cattiva" per l'attività, il programma eseguirà un ciclo dell'automa, essendo nello stato q1 e cadendo continuamente su celle vuote, si sposterà a destra indefinitamente. (Naturalmente, in questo caso, il programma potrebbe essere interrotto, ma abbiamo appositamente creato un ciclo per dimostrare questa possibilità.) Se c'è esattamente un carattere nella parola di input, l'automa cancellerà questo carattere, spostando una cella nella a destra e scrivici questo carattere: cc q1 q4! Pertanto, una parola di un carattere si sposterà semplicemente di una cella a destra. Questo è accettabile. Dopotutto, le celle del nastro non sono numerate, quindi la posizione della parola sul nastro non è fissata in alcun modo e il movimento della parola a sinistra oa destra non può essere notato. A questo proposito, non è necessario che la parola di uscita si trovi nello stesso punto in cui si trovava la parola di ingresso, il risultato può essere sia a sinistra che a destra di questo luogo. Esempio 3 (confronto di caratteri, cancellazione di parole) A=(a,b,c). Se il primo e l'ultimo simbolo di una parola P (non vuota) sono gli stessi, allora questa parola non viene modificata, altrimenti viene sostituita dalla parola vuota. Soluzione. Per risolvere questo problema, si propone di eseguire le seguenti azioni: 1. Ricordare il primo carattere della parola di input senza cancellarlo. 2. Spostare l'automa sotto l'ultimo carattere e confrontarlo con quello memorizzato. Se sono uguali, non fare nient'altro. 3. In caso contrario, distruggere l'intera parola di input. Sappiamo già come memorizzare un carattere e come superare la macchina fino all'ultimo carattere di una parola degli esempi precedenti. La cancellazione della parola di input è implementata 9
10 sostituendo tutti i suoi simboli con il simbolo Λ. Allo stesso tempo, poiché l'automa è alla fine della parola, sposteremo l'automa da destra a sinistra nella prima cella vuota. Queste azioni sono descritte dal seguente programma per MT (ricordiamo che una crocetta in una cella di tabella significa che la configurazione corrispondente non può apparire quando il programma viene eseguito): a b c Λ q1,q2,q4,q6,! analisi del 1° carattere, ramificazione q2,r,r,r, L,q3 vai all'ultimo carattere al 1° carattere a q3,!, q8, q8 confronta per ultimo. carattere con a non sono uguali su q8 (cancella P) q4,r,r,r, L,q5 allo stesso modo per il 1° carattere b q5, q8,!, q8 q6,r,r,r, L,q7 allo stesso modo per il 1° carattere cq7,q8,q8,! q8 Λ,L, Λ,L, Λ,L,! cancellare l'intera parola, spostandosi da destra a sinistra Esempio 4 (cancellazione di un carattere da una parola) A=(a,b). Rimuovere dalla parola P il suo secondo carattere, se presente. Soluzione. Sembrerebbe che questo problema sia di facile soluzione: è necessario spostare l'automa sotto la cella con il secondo simbolo e quindi cancellare questa cella: a b b a a b b a a b a Ricordiamo però che non devono esserci celle vuote all'interno della parola di output. Pertanto, dopo aver cancellato il secondo carattere, è necessario “comprimere” la parola spostando il primo carattere di una cella a destra. Per fare ciò, l'automa deve tornare al primo simbolo, ricordarlo e cancellarlo, quindi, spostandosi di nuovo a destra, scriverlo nella cella in cui si trovava il secondo simbolo. Tuttavia, la “camminata” iniziale a destra del secondo simbolo per cancellarlo, e il successivo ritorno al primo simbolo sono azioni inutili: che differenza fa trasferire il primo simbolo in una cella vuota o in una cella con qualche simbolo? Pertanto, ricordiamo subito il primo carattere, lo cancelliamo e lo scriviamo al posto del secondo carattere: abbabbaaba Nella forma di un programma per MT, tutto questo è scritto come segue: ab Λ q1 Λ,R,q2 Λ,R, q3,! analisi e rimozione del 1° carattere, ramificazione q2,! un! un! sostituzione del 2° carattere con un q3 b,!,! B! sostituendo il 2° carattere con b Esempio 5 (compressione di parole) A=(a,b,c). Elimina dalla parola P la prima occorrenza del carattere a, se presente. Soluzione. Nell'esempio precedente, abbiamo spostato solo un carattere nella posizione a destra - 10
11 w. In questo esempio, faremo un ciclo a destra per trasferire tutti i caratteri iniziali b e c della parola di input al primo carattere a o in una cella vuota: bcbcbaabbaabcaabcba questo simbolo y potrebbe essere spostato nella cella di destra? Se qx denota lo stato in cui è necessario scrivere il simbolo x, che prima era nella cella a sinistra, nella cella visibile, allora questa azione può essere rappresentata come segue: in primo luogo, il simbolo x preso dalla cella su la sinistra è scritta nella cella visibile; in secondo luogo, l'automa si sposta a destra sotto la cella, nella quale bisognerà poi scrivere il simbolo y appena sostituito; in terzo luogo, l'automa va nello stato q y, in cui eseguirà questa registrazione. La ripetizione di tali misure in un ciclo comporterà uno spostamento a destra di una posizione dei caratteri iniziali della parola di input. Questo ciclo dovrebbe terminare quando il carattere a o Λ (y=a o y=λ) appare nella cella successiva, e all'inizio del ciclo, possiamo supporre che il carattere "vuoto" (x=λ) sia trasferito a il posto del primo carattere a sinistra. Il risultato è il seguente programma per MT: a b c Λ q1 Λ,R,! Λ,R,q2 Λ,R,q3,! q Λ : cancella il 1° carattere e spostalo a destra q2 b,!,r, b,r,q3 b,! q b: scrivi b, sposta a destra il carattere precedentemente visibile q3 c,! c,r,q2,r, c,! q c: scrivi c, sposta a destra il carattere precedentemente visibile In questo programma dovresti prestare attenzione al ciclo Λ,R,!
12 il primo carattere (non puoi ancora eliminarlo nella vecchia posizione), quindi, tornando alla vecchia posizione, scrivi il carattere a: bcabcabbcabaca Spostare il carattere di una posizione a sinistra è simile a spostare il carattere a destra, come discusso nei due esempi precedenti, quindi forniremo un programma per MT senza commenti aggiuntivi. Notiamo solo che negli stati q2, q3 e q4 l'automa può vedere solo una cella vuota, e nello stato q5 vede necessariamente il primo simbolo della parola in ingresso, ma non una cella vuota. a b c Λ q1,l,q2,l,q3,l,q4,! analizzare il 1° carattere per spostarlo a sinistra q2 a,r,q5 assegnare a a sinistra q3 b,r,q5 assegnare b a sinistra q4 c,r,q5 assegnare c a sinistra q5,! un! un! sostituire il primo carattere precedente con un Esempio 7 (diffusione di parole) А=(a,b,c). Inserire il carattere a nella parola P dopo la prima occorrenza del carattere c, se presente. Soluzione. Esaminiamo la parola di input da sinistra a destra fino a una cella vuota o al primo carattere c. Nel primo caso, c non è incluso in P, quindi non facciamo nulla. Nel secondo caso, occorre fare spazio al carattere inserito a, per il quale spostiamo l'inizio della parola P (dal primo carattere al carattere trovato c) di una posizione a sinistra. In questo caso, eseguiamo un tale spostamento da destra a sinistra dal simbolo c all'inizio della parola, poiché l'automa si trova sotto questo simbolo. Inoltre, per non tornare successivamente alla posizione libera, iniziamo questo spostamento scrivendo a al posto del carattere trovato c. Poiché questo spostamento ciclico a sinistra è implementato in modo simile allo spostamento ciclico a destra dell'Esempio 5, non lo spiegheremo, ma forniremo immediatamente il programma per MT: abc Λ q1,r,r, a,l,q4,l ,! da destra in c, inserisci a invece di c, sposta c a sinistra q2,l, a,l,q3 a,l,q4 a,! sposta a a destra q3 b,l,q2,l, b,l,q4 b,! spostamento a destra b q4 c,l,q2 c,l,q3,l, c,! trasferire c a destra Esempio 8 (formazione di una parola in una nuova posizione) А=(a, b, c). Rimuovi da P tutte le occorrenze del carattere a. Soluzione. Gli esempi precedenti mostrano che l'inserimento di caratteri nelle parole e l'eliminazione di caratteri dalle parole sono piuttosto difficili in MT. Pertanto, a volte è più facile non espandere o comprimere la parola di input, ma formare la parola di output.
13 in un altro posto libero sul nastro. Questo è esattamente ciò che faremo per risolvere questo problema. Nello specifico, si propone di eseguire le seguenti azioni: 1. Costruiremo la parola di output a destra della parola di input. Per delimitare queste parole, le separiamo con qualche simbolo ausiliario, ad esempio il segno =, diverso da tutti i simboli dell'alfabeto A (vedi punto 1). (Ricordiamo che non solo i caratteri dell'alfabeto della parola di input possono essere scritti sul nastro.) 2. Dopodiché, torniamo all'inizio della parola di input (vedi punto 2). a b c a b c = a b c = Ora il nostro compito è trasferire in un ciclo tutti i caratteri della parola di input, ad eccezione di a, a destra dietro il segno = nella parola di output generata. Per fare ciò, analizziamo il primo carattere della parola di input. Se è un, cancellalo e passa al carattere successivo (vedi passaggio 3). Se il primo carattere è b o c, lo cancelliamo e "corriamo" a destra fino alla prima cella vuota (vedi passaggio 4), dove scriviamo questo carattere (vedi passaggio 5). b c = c = c = b Torniamo di nuovo a sinistra al carattere che è diventato il primo nella parola di input e ripetiamo le stesse azioni, ma rispetto a questo carattere (vedere i passaggi 6-9). c = b = b = b c Questo ciclo termina quando torniamo a sinistra e vediamo = come primo carattere. Questo è un segno che abbiamo scansionato completamente la parola di input e trasferito tutti i suoi caratteri diversi da a nella parola di output formata a destra. È necessario cancellare questo segno, spostarsi a destra sotto la parola di uscita e fermarsi (vedere il passaggio 10). = b c b c 9 10 Tenendo conto di quanto detto, stiamo costruendo un programma per MT. Allo stesso tempo, notiamo che oltre ai simboli a, b e c, sul nastro appare il segno = nel processo di risoluzione del problema, quindi la tabella deve avere anche una colonna per questo segno. abc = Λ q1,r,r,r, =,q2 scrivi il segno = q2,l,l,l,l,r,q3 da destra al 1° simbolo della parola q3 Λ,R, Λ,R, q4 Λ, R,q5 Λ,R,! analizzalo e rimuovilo, dirama q4,r,r,r,r, b,q2 scrivi b a destra, torna a sinistra (in un ciclo) q5,r,r,r,r, c,q2 scrivi c in a destra, torna a sinistra (in ciclo) 13
14 Esempio 9 (fissaggio del punto sul nastro) A=(a,b). Raddoppia la parola P inserendo un segno = tra essa e la sua copia. Ad esempio: a a b a a b = a a b Soluzione. Questo problema si risolve in modo simile al precedente: scriviamo il segno = alla fine della parola di input, quindi torniamo all'inizio della parola e copiamo tutti i suoi caratteri (compreso a) nel ciclo nelle celle vuote a destra : aabaab = aab = aab = a 1 2 Tuttavia, c'è anche una differenza: i caratteri copiati della parola di input non vengono rimossi, e questo porta al seguente problema. Dopo aver scritto una copia del carattere successivo a destra, dobbiamo quindi tornare alla parola di input nella posizione di questo carattere e quindi spostarci a destra al carattere successivo per copiarlo già. Ma come fai a sapere in quale posizione della parola di input tornare? Ad esempio, come facciamo a sapere nel nostro esempio che dopo aver copiato il primo carattere a dovremmo tornare esattamente al primo carattere della parola di input e non al secondo o al terzo? Nell'attività precedente, siamo sempre tornati al primo dei caratteri rimanenti della parola di input e ora salviamo tutti i caratteri, quindi non è chiaro quali caratteri abbiamo già copiato e quali no. Notiamo anche che in MT le celle del nastro non sono numerate in alcun modo, non ci sono contatori in MT che ci permetterebbero di determinare quanti caratteri abbiamo già copiato. In termini generali, il problema che ci troviamo di fronte è il seguente: come fissare sul nastro una certa posizione in cui siamo già stati e su cui dobbiamo tornare in seguito? Di solito questo problema viene risolto in questo modo. Quando ci troviamo in questa posizione per la prima volta, sostituiamo il carattere in esso contenuto con il suo doppio con un nuovo simbolo ausiliario e sostituiamo caratteri diversi con doppi diversi, ad esempio a con A e b con B. Successivamente, eseguiamo alcune azioni in altri punti del nastro. Per poi tornare alla nostra posizione, ti basta trovare sul nastro la cella dove si trova il simbolo A o B. Quindi in questa cella puoi ripristinare il simbolo precedente se non abbiamo più bisogno di fissare questa posizione (era per ripristinare il simbolo precedente che dovevamo sostituire simboli diversi in controparti diverse). Usiamo questa tecnica nel nostro compito, eseguendo le seguenti azioni: 1. Come già accennato, prima scriviamo il segno = dietro la parola di input (vedi punto 1 sopra). 2. Quindi torniamo sotto il primo carattere della parola di input (vedere il passaggio 2 sopra). 3. Successivamente, sostituiamo il simbolo visibile a con una doppia A (vedi passaggio 3 di seguito), "corri" a destra fino alla prima cella libera e scrivi il simbolo a al suo interno (vedi passaggio 4). Dopodiché, torniamo a sinistra nella cella con la doppia A (vedi Fig. punto 5), ripristinare il carattere precedente a e spostarsi a destra al carattere successivo (vedere punto 6). 14
15 aab = A ab = A ab = a A ab = aaab = aa A b = aa A b = aaaa B = aabaab = aab Ora copia il secondo carattere allo stesso modo (sostituiscilo con A, aggiungi a alla fine, ecc.) ) e tutti i caratteri successivi della parola in ingresso. 4. Quando copiamo l'ultimo carattere della parola di input e torniamo al suo gemello (dopo il passaggio 12), dopo aver spostato di una posizione a destra, arriveremo al segno = (passo 13). Questo è un segnale che la parola in ingresso è stata completamente copiata, quindi il lavoro dell'MT deve essere completato. Tenendo conto di tutto quanto detto, otteniamo per MT il seguente programma: ab = AB Λ q1,r,r, =,L,q2 put = a destra della parola q2,l,l,r,q3 a a sinistra sotto il 1° carattere q3 A,R, q4 B,R,q5,! analisi e sostituzione del carattere successivo q4,r,r,r, a,q6 scrivi a a destra q5,r,r,r, b,q6 scrivi b a destra q6,l,l,l, a,r ,q3 b,r, q3 ritorna, ripristina, al successivo. Notiamo che in questo programma possiamo eliminare lo stato q6 combinandolo con lo stato q2, prevedendo che q2 torni a sinistra sia alla cella vuota che ai simboli A e B: ab = AB Λ.. q2,l,l ,l, a,r,q3 b,r,q3,r,q3 lasciati a Λ, A o B Problemi per soluzione indipendente Note: 1) Nei problemi sono considerati solo gli interi non negativi, a meno che diversamente indicato. 2) Il sistema numerico “singolo” è inteso come la registrazione di un numero intero non negativo con l'ausilio di bastoncini, da scrivere tanti bastoncini quanta è la grandezza del numero; es: 2, 5, 0<пустое слово>. 1.1 A=(a,b,c). Attribuire il simbolo b (P bp) a sinistra della parola P. 1.2 A=(a,b,c). Assegnare i simboli bc (P Pbc) a destra della parola P. 1.3 A=(a,b,c). Passare a un carattere ogni secondo nella parola P. 15
16 1.4 A=(a,b,c). Lascia solo il primo carattere nella parola P (non modificare la parola vuota). 1.5A=(a,b,c). Lascia solo l'ultimo carattere nella parola P (non modificare la parola vuota). 1.6 A=(a,b,c). Determina se P è una parola ab. Risposta (parola di uscita): la parola ab se lo è, altrimenti la parola vuota. 1.7 A=(a,b,c). Determina se la parola P contiene il carattere a. Risposta: una parola di un carattere a (sì, inclusa) o una parola vuota (no). 1.8 A=(a,b,c). Se la parola P non include il simbolo a, sostituisci tutti i simboli b in P con c, altrimenti dai come risposta la parola di un simbolo a. 1.9 A=(a,b,0,1). Determina se la parola P è un identificatore (una parola non vuota che inizia con una lettera). Risposta: parola a (sì) o parola vuota (no) A=(a,b,0,1). Determina se la parola P è una rappresentazione di un numero in notazione binaria (una parola non vuota composta solo dalle cifre 0 e 1). Risposta: parola 1 (sì) o parola A=(0,1). Considerando una parola non vuota P come una rappresentazione di un numero binario, rimuovere da essa gli zeri insignificanti, se esistono tali A=(0,1). Per una parola P non vuota, determinare se è una rappresentazione di una potenza di due (1, 2, 4, 8,) nel sistema di numeri binari. Risposta: parola 1 (è) o parola A=(0,1,2,3). Considerando una parola non vuota P per rappresentare un numero nel sistema numerico quaternario, determinare se è un numero pari o meno. Risposta: 1 (sì) o A=(0,1). Considerando una parola non vuota P come rappresentazione di un numero nel sistema binario, si ottiene un numero binario pari a quattro volte il numero P (ad esempio: A=(0,1). Considerando una parola non vuota P come una rappresentazione di un numero nel sistema binario, ottieni un numero binario uguale al quoziente incompleto della divisione del numero P per 2 (ad esempio:) A=(a,b,c). Se P è una parola di lunghezza pari (0, 2, 4,), allora restituisce la risposta a, altrimenti la parola vuota A=(0,1,2). Considerando una parola non vuota P come una rappresentazione di un numero nel sistema numerico ternario, determinare se è un numero pari o meno. Risposta: 1 (sì) o 0. (Nota: un numero ternario pari deve avere un numero pari di cifre 1.) 1.18 A=(a,b,c). Sia P di lunghezza dispari. Lascia solo il simbolo centrale A=(a,b,c) in P. Se la parola P ha lunghezza pari, allora lascia in essa solo la metà sinistra A=(a,b,c). Assegna a sinistra della parola non vuota P il suo primo carattere. sedici
17 1.21 A=(a,b). Per una parola P non vuota, determinare se il suo primo carattere la reimmette. Risposta: a (sì) o la parola vuota A=(a,b). In una parola non vuota P, scambia il suo primo e l'ultimo simbolo A=(a,b). Determina se P è un palindromo (parola variabile, simmetrica) o meno. Risposta: a (sì) o la parola vuota A=(a,b). Sostituisci in P ogni occorrenza di a con bb A=(a,b,c). Sostituisci in P ogni occorrenza di ab con c A=(a,b). Raddoppia la parola P (ad esempio: abb abbabb) A=(a,b). Raddoppia ogni carattere della parola P (es: bab bbaabb) A=(a,b). Capovolgere la parola P (ad esempio: abb bba) A=(0,1). Considerando una parola non vuota P come un numero binario, ottieni lo stesso numero, ma nel sistema quaternario. (Nota: tieni presente che può esserci un numero dispari di cifre in un numero binario.) 1.30 A=(0,1,2,3). Considerando una parola non vuota P come una rappresentazione di un numero nel sistema numerico quaternario, si ottiene la rappresentazione di questo numero nel sistema binario A=(0,1,2). Considerando una parola non vuota P come un numero positivo in notazione ternaria, diminuire questo numero di A=( ). Considerando la parola P come una rappresentazione di un numero nel sistema dei numeri unitari, ottieni la rappresentazione di questo numero nel sistema ternario. (Raccomandazione: rimuovere un bastoncino dal numero “singolo” in un ciclo e aggiungere ogni volta 1 al numero ternario, che prima è posto uguale a 0.) 1.33 A=(0,1,2). Considerando una parola P non vuota come una rappresentazione numerica nel sistema numerico ternario, si ottiene una rappresentazione di tale numero nel sistema delle unità. Sia la parola P avere la seguente forma: (... (... nm dove uno dei segni +, /, o, a sinistra dei quali sono indicati n stick , e m stick a destra Eseguire l'operazione corrispondente nel sistema di numerazione delle unità (in risposta, dare la parola indicata a destra della freccia): a) addizione: (... + (... (... (n 0, m 0) nm n+ mb) sottrazione: (... (... (... (nm 0) nmnm c) moltiplicazione : (... (... (... (n 0, m 0) nmnm d) divisione intera: ((... /... (... (n 0, m>0, k=n div m) nmk e) prendendo il resto: (... (... (... (n 0, m>0, k=n mod m) nmk 17
18 f) massimo: (... (... (... (n 0, m 0, k=max(n, m)) nmk g) minimo: (... (... (... (n 0, m 0, k=min(n,m)) knm 1.35 A=( ) Assumendo che la parola P rappresenti un numero nel sistema di identità, determinare se questo numero è una potenza di 3 (1, 3, 9 , 27,) Risposta: una parola vuota, se lo è, o una parola di un bastoncino altrimenti A=( ). Considerando la parola P come una rappresentazione del numero n nel sistema di identità, si ottiene il numero 2 n A=( ) nello stesso sistema Sia la parola P una rappresentazione del numero 2 n (n=0, 1, 2,) nel sistema di identità Ottieni il numero n nello stesso sistema Sia P della forma Q+R, dove Q e R sono parole non vuote dei simboli 0, 1 e 2. Trattando Q e R come numeri di notazione nel sistema numerico ternario (possibilmente con zeri insignificanti), dare come risposta il record della somma di questi numeri in lo stesso sistema ternario come record di numeri nel sistema numerico ternario (possibilmente con zeri insignificanti) e supponendo che QR, dare come risposta il record della differenza di questi numeri in quello nello stesso sistema ternario Sia P la forma Q=R, dove Q e R sono parole qualsiasi dei simboli aeb. Dare la risposta a se le parole Q e R sono uguali e la parola vuota in caso contrario Sia P della forma Q=R, dove Q e R sono parole non vuote dei simboli 0 e 1. Trattando Q e R come notazioni di numeri binari (possibilmente con zeri non significativi), rispondere alla parola 1 se questi numeri sono uguali e alla parola 0 altrimenti Sia P della forma Q>R, dove Q e R sono parole non vuote dei simboli 0 e 1 .zeri), dare come risposta la parola 1 se il numero Q è maggiore del numero R, altrimenti la parola 0 A=((,)). Determina se la parola P è bilanciata da parentesi. Risposta: D (sì) o N (no) A=(a,b). Se ci sono più caratteri a in P rispetto ai caratteri b, restituisci la risposta a, se i caratteri a sono inferiori ai caratteri b, restituisci la risposta b, altrimenti restituisci la parola vuota. 2. Algoritmi di Markov normali In questa sezione, consideriamo il problema della scrittura di algoritmi di Markov normali. Viene fornita una breve descrizione di questi algoritmi, vengono spiegati i principali metodi della loro compilazione con esempi e vengono proposti problemi per una soluzione indipendente. diciotto
19 2.1 Breve descrizione dei normali algoritmi di sostituzione di Markov Una caratteristica interessante dei normali algoritmi di Markov (NAM) è che utilizzano una sola operazione elementare, la cosiddetta sostituzione, che è definita come segue. Una formula di sostituzione è un record della forma α β (si legge "sostituisci α con β"), dove α e β sono qualsiasi parola (possibilmente vuota). In questo caso, α è chiamato il lato sinistro della formula e β è chiamato il lato destro. La sostituzione stessa (come azione) è specificata da una formula di sostituzione e applicata a qualche parola P. L'essenza dell'operazione è che nella parola P si trova la parte che corrisponde al lato sinistro di questa formula (cioè, con α) , ed è sostituito dalle formule del lato destro (cioè su β). In questo caso, le parti rimanenti della parola P (a sinistra ea destra di α) non cambiano. La parola risultante R è chiamata risultato della sostituzione. Convenzionalmente, questo può essere rappresentato come segue: P x α y R x β y Chiarimenti necessari: 1. Se il lato sinistro della formula di sostituzione è incluso nella parola P, allora dicono che questa formula è applicabile a P. Ma se α non è incluso in P, quindi la formula è considerata non applicabile a P e non viene eseguita alcuna sostituzione. 2. Se il lato sinistro di α ricorre più volte in P, per definizione, solo la prima occorrenza di α in P è sostituita dal lato destro di β: P x α y α z R x β y α z 3. Se il lato destro della formula di sostituzione è una parola vuota, quindi la sostituzione α si riduce a cancellare la parte α da P (notiamo di passaggio che non è consuetudine indicare la parola vuota nelle formule di sostituzione): P x α y R xy 4. Se la parola vuota è indicata a sinistra della formula di sostituzione, allora la sostituzione β si riduce, per definizione, ad attribuire β a sinistra alla parola P: P x R β x Da questa regola deriva un fatto molto importante : una formula con il lato sinistro vuoto è applicabile a qualsiasi parola. Nota anche che una formula con i lati sinistro e destro vuoti non cambia la parola. Definizione di NAM Un normale algoritmo di Markov (NAM) è un insieme ordinato finito non vuoto di formule di sostituzione: 19
20 α1 β1 α 2 β 2... (k 1) α k β k In queste formule possono essere utilizzati due tipi di frecce: una freccia regolare () e una freccia a coda (a). Una formula con una freccia normale è chiamata formula regolare e una formula con una freccia di coda è chiamata formula finale. La differenza tra loro è spiegata di seguito. Scrivere un algoritmo sotto forma di NAM significa presentare un tale insieme di formule. Regole per l'esecuzione di NAM Prima di tutto, viene data una parola di input P. Dove è scritto esattamente non è importante, questa domanda non è specificata in NAM. Il lavoro di NAM si riduce all'attuazione di una sequenza di passaggi. Ad ogni passaggio, le formule di sostituzione incluse nel NAM vengono scansionate dall'alto verso il basso e viene selezionata la prima delle formule applicabili alla parola di ingresso P, ovvero il più in alto di quelli, la cui parte sinistra è inclusa in R. Successivamente, la sostituzione viene eseguita secondo la formula trovata. Si ottiene una nuova parola P. Nella fase successiva, questa parola P viene presa come parola originale e ad essa viene applicata la stessa procedura, cioè si ricercano nuovamente le formule dall'alto verso il basso, partendo da quella più in alto, e si ricerca la prima formula applicabile alla parola P, dopodiché si effettua l'opportuna sostituzione e si ottiene una nuova parola P. E così via: Р Р Р Particolare attenzione va prestata al fatto che ad ogni passaggio della formula negli USA vengono sempre visualizzati a partire dal primo. Chiarimenti necessari: 1. Se nella fase successiva è stata applicata la consueta formula (α β), il lavoro NAM continua. 2. Se la formula finale (α a β) è stata applicata al passaggio successivo, dopo la sua applicazione, il lavoro del NAM si interrompe. La parola che è uscita in questo momento è la parola in uscita, cioè il risultato dell'applicazione di NAM alla parola di ingresso. Come puoi vedere, la differenza tra la formula di sostituzione abituale e quella finale si manifesta solo nel fatto che dopo aver applicato la formula abituale, il lavoro del NAM continua e dopo la formula finale si interrompe. 3. Se al passaggio successivo non è applicabile alcuna formula alla parola corrente, anche in questo caso viene terminato il lavoro del NAM e la parola corrente viene considerata la parola di uscita. Pertanto, NAM si interrompe per due motivi: è stata applicata la formula finale o nessuna delle formule si adatta. Entrambi sono considerati finali "buoni" per NAM. In entrambi i casi, si dice che il NAM si applichi alla parola di input. venti
Università statale di Mosca intitolata a M.V. Lomonosov Facoltà di matematica computazionale e cibernetica V.N. Pilshchikov, V.G. Abramov, AA Vylitok, IV Macchina di Turing a caldo e algoritmi di Markov.
MACCHINA DI TURING NELLO STUDIO DELLA TEORIA DEGLI ALGORITMI Lebedeva N.Yu. Shuya Branch dell'Università statale di Ivanovo MACCHINA DI TURING NELLO STUDIO DELLA TEORIA DEGLI ALGORITMI Lebedeva N. Yu. ramo di Shuya
AGGIUNTA Sommare 1 a un numero significa ottenere il numero successivo a quello dato: 4+1=5, 1+1=14, ecc. Sommare i numeri 5 significa sommare da uno a 5 tre volte: 5+1+1+1=5+=8. SOTTRATTA Sottrarre 1 da un numero significa
Problemi e soluzioni del turno di qualificazione dell'Olimpiade DM&T 2014-2015 Tutti i problemi, i manipolatori e le soluzioni sono disponibili per i partecipanti sul sito web dell'Olimpiade. Tutti i compiti proposti sono stati valutati con lo stesso numero di punti. Conta.
Macchina di Turing 1 Una macchina di Turing è un concetto matematico, non una vera macchina informatica. MT è un modello matematico di un dispositivo informatico. MT è stato proposto da Alan Turing nel 1936
Risoluzione dei problemi della macchina di Turing online >>> Risoluzione dei problemi della macchina di Turing online Risoluzione dei problemi della macchina di Turing online Il contenuto di una cella può cambiare, puoi scriverci un altro carattere o eliminarlo
Sistemi numerici Nel nostro tempo, una persona si trova costantemente di fronte ai numeri. Fin dall'infanzia, abbiamo tutti familiarità con la notazione generalmente accettata dei numeri utilizzando i numeri arabi. Tuttavia, questo metodo di registrazione non è stato ampiamente utilizzato.
Algoritmo implementato Usiamo la seguente variazione dell'algoritmo di Euclide per calcolare il gcd dei numeri M e N:. un M, b N; 2. t a-b, se t = 0, stop; 3. a t, b min(a,b), andare al passaggio 2. Dopo aver interrotto GCD(M,N)
Problemi del turno di qualificazione delle Olimpiadi in Matematica Discreta e Informatica Teorica con soluzioni (quando si risolvono problemi costruttivi, il partecipante lavora con emulatori, le immagini delle loro interfacce sono mostrate nelle soluzioni)
Capitolo B. Lezione di aritmetica del computer B3. Aritmetica binaria Vediamo come hai fatto con gli esercizi della lezione B2. Ecco le loro soluzioni. Esercizi B2-2 a) La tabella di posizionamento dei kettlebell si presenta così: numerata
Lezione 23 Nelle condizioni dei problemi M, x significano, rispettivamente, la descrizione della macchina di Turing e la parola di input nel formato introdotto a lezione (e scritto nella bozza del libro di testo). Problema 23.1. Prova che
Sezione 6. Teoria degli algoritmi. Un concetto informale di algoritmo, le sue principali caratteristiche e proprietà. Alfabeto, parole, algoritmo nell'alfabeto. Algoritmi abbastanza equivalenti. Definizione di un algoritmo normale (algoritmo
SISTEMI NUMERICI POSIZIONALI Esistono molti modi per rappresentare i numeri. In ogni caso, il numero è rappresentato da un simbolo o da un gruppo di simboli (parola) di qualche alfabeto. Chiameremo tali simboli
Compiti per il grado 11 Fase di selezione. Primo round 1. Informazioni di codifica. Sistemi numerici (2 punti) [Permutazioni] Quanti numeri esadecimali a tre cifre ci sono che saranno contemporaneamente
Risoluzione di problemi sul tema "Rappresentazione di numeri in un computer" Tipi di problemi: 1. Interi. Rappresentazione di numeri in formato a virgola fissa. 2. Numeri frazionari. Rappresentazione di numeri in formato a virgola mobile.
1. Cavalieri e furfanti. Diagramma logico - 1. Compiti e soluzioni del round a tempo pieno delle Olimpiadi di Dmitri-2017-2018 Quattro persone sono sedute alla tavola rotonda. Ognuno di loro è un cavaliere o un furfante. I cavalieri dicono sempre solo
Sistemi numerici Il sistema numerico è un modo per scrivere numeri utilizzando un determinato insieme di caratteri speciali (numeri). Nella tecnologia informatica vengono utilizzati sistemi numerici posizionali, in cui il valore di una cifra
LEZIONE 3. Algoritmi per l'elaborazione di array unidimensionali. Scopo della lezione: Conoscenza del concetto di array. Acquisizione di competenze nella costruzione di algoritmi progettati per elaborare array unidimensionali. 6. Algoritmi
Versione dimostrativa dell'attività 6 di USE 2019 L'input dell'algoritmo è un numero naturale N. L'algoritmo crea un nuovo numero R da esso come segue. 1) Si costruisce una notazione binaria del numero N. 2) A questa notazione
Introduzione ai sistemi numerici A.A. Lingotto Il sistema numerico è un modo di scrivere numeri utilizzando un determinato insieme di caratteri speciali (numeri). Esistono sistemi numerici posizionali e non posizionali. In non posizionale
Parte III Lingue, grammatiche, automi 137 Capitolo 10 Lingue e automi finiti 10.1 La lingua di Dick Come sappiamo, le strutture corrette delle parentesi sono enumerate dai numeri catalani. Scriviamo tutte le parentesi corrette
Fase municipale delle Olimpiadi All-Russe per gli scolari in Informatica Mosca, dicembre 00. Compiti per i gradi 7-8 Ogni compito è stimato in 0 punti. Il punteggio finale è fissato come somma dei punti per le attività
Macchine virtuali Introduzione Oltre quarant'anni fa, l'eminente matematico americano Emil L. Post pubblicò sul Journal of Symbolic Logic un articolo "Processi combinatori finiti, formulazione!" (sua
Ugra Physics and Mathematics Lyceum VP Chuvakov Task C6 (Teoria dei numeri sull'esame di stato unificato) Guida educativa e metodologica Khanty-Mansiysk 0 VP Chuvakov Problema C6 (Teoria dei numeri sull'esame di stato unificato): Guida allo studio, - Khanty-Mansiysk,
9 CLASSE 1. In una delle celle del quadretto infinito è presente un robot, al quale possono essere impartiti i seguenti comandi: su (il robot si sposta dall'alto alla cella successiva); giù (il robot si sposta su
Sistemi numerici Il sistema numerico è un modo per scrivere numeri utilizzando un determinato insieme di caratteri speciali (cifre). Esistono sistemi numerici posizionali e non posizionali. Nei sistemi non posizionali, il peso
Sistemi numerici Il sistema numerico è un modo per descrivere i numeri usando i caratteri di un certo alfabeto secondo regole note. Sistemi numerici posizionali Nel sistema numerico posizionale, il valore di una cifra dipende
K. Polyakov, 009-06 6- (livello base, tempo 4 min) Argomento: Trovare un algoritmo di lunghezza minima per un artista. Cosa devi sapere: l'esecutore è una persona, un gruppo di persone, un animale, una macchina o un altro oggetto,
Lezione 5 Fondamenti di rappresentazione dell'informazione negli automi digitali Sistemi numerici posizionali Il sistema numerico è un insieme di tecniche e regole per scrivere numeri in caratteri digitali. Qualsiasi previsto
Elementi di teoria della complessità Macchina di Turing Alan Turing (23.06.1912-7.06.1954) (Alan Mathison Turing) Matematico, logico, crittografo inglese. Nel 1936 propone una "Macchina di Turing" computazionale astratta,
Ministero dell'Istruzione e della Scienza della Federazione Russa Istituto statale per l'istruzione professionale della Federazione Russa "Università statale di Rostov" M. E. Abramyan
10 CLASSE 1. I numeri reali soddisfano le seguenti relazioni: Trova tutte le possibili terzine di numeri, dove Soluzione. Si noti che denotando e sottraendo queste uguaglianze l'una dall'altra, otteniamo Assume che tutto
Appendice all'articolo Gorbunov K.Yu., Lyubetsky V.A. "Un algoritmo lineare per la ristrutturazione minima delle strutture" Dimostrazione del Lemma 3. Chiamiamo un blocco rigido, delimitato su entrambi i lati da geni comuni, semirigido
Appendice 1 Workshop per il capitolo 2 "Rappresentazione di informazioni in un computer" Lavoro pratico per il paragrafo 2.1 Esempio 2.1. Esprimi i numeri 2466.675 10, 1011.11 2 in termini di potenze della base Per decimale
Corrispondenza Liceo Fisico e Matematico "Avangard" EN Filatov ALGEBRA 8 Manuale sperimentale Parte 1 MOSCA 2016 CONTENUTI 1. Divisibilità. 2. Pari dispari 3. Set. 4. Compiti divertenti. 5. Combinatoria
Libro delle attività sull'informatica dello studente (tsy) dell'11a classe fisica e matematica della scuola secondaria 36 di Vladimir Parte II 2016-2017 2 1. Algoritmo. 1.1 Si propone qualche operazione su due arbitrari
Argomento 7. Rappresentazione di informazioni in un computer Unità di informazioni. Bit - (cifra bit-biry - cifra binaria) la più piccola unità di informazione - la quantità di informazioni necessaria per distinguere tra due eventi ugualmente probabili.
I. V. Yakovlev Materiali sulla matematica MathUs.ru Contenuti Notazione decimale 1 Olimpiadi di tutta la Russia per gli scolari in matematica.......... 1 2 Olimpiadi di matematica di Mosca.......... ....... ........
Argomento 1: Sistemi di equazioni lineari A. Ya. Ovsyannikov Istituto Universitario Federale degli Urali di Matematica e Informatica Dipartimento di Algebra e Matematica Discreta Algebra e geometria per fisici-ingegneri
Capitolo 5 Elementi di teoria degli algoritmi 31 Chiarimento del concetto di algoritmo Parole chiave: algoritmo teoria degli algoritmi esecutore universale macchina di Turing Post macchina normale algoritmo di Markov Perché
Risoluzione di problemi sull'argomento "Rappresentazione di numeri in un computer". Tipi di attività. 1. Interi. Rappresentazione di numeri in formato a virgola fissa. 2. Numeri frazionari. Rappresentazione di numeri in formato mobile
A. Shen Giochi e strategie dal punto di vista della matematica, MTsNMO Giochi semplici e classifica delle posizioni Ci sono 12 partite sul tavolo. I giocatori si alternano da una a tre partite. Chi non può fare una mossa
Teoria degli algoritmi 79 3.2. Algoritmi normali j Sia A un alfabeto che non contiene simboli. e. Una formula di sostituzione ordinaria è una rappresentazione della forma P Q, dove P e Q sono alcune parole dell'alfabeto A. La finale
LEZIONE 2. Algoritmi di struttura ciclica. Scopo della lezione: Conoscenza del concetto di algoritmo a struttura ciclica. Acquisizione di competenze nella costruzione di algoritmi per una struttura ciclica. 5. Algoritmi del ciclico
Lezioni di matematica. Problema. TMM-1 Yu. V. Chebrakov TEORIA DELLE MATRICI MAGICHE San Pietroburgo, 2010 tecnico.
Lavoro pratico. Forme di rappresentazione di informazioni numeriche su un computer. Parte I. Sistemi numerici. Un sistema numerico è un modo per rappresentare qualsiasi numero usando un alfabeto
Istituto di Fisica e Tecnologia di Mosca Facoltà di Innovazione e Alte Tecnologie Logica Matematica e Teoria degli Algoritmi, autunno 2018 Seminario 1: un linguaggio per scrivere dichiarazioni formali, con soluzioni ad alcuni
Lezione 16
16 (livello alto, tempo min) Argomento: Numeri di codifica. Sistemi numerici. Cosa devi sapere: i principi di codifica dei numeri nei sistemi numerici posizionali per tradurre un numero, diciamo, 15, dal sistema
2015 Espressioni regolari Soluzioni ai problemi del girone di qualificazione (due opzioni) Opzione 1 Costruire un'espressione regolare che descriva l'insieme di parole dalle lettere aeb, da cui tutte le parole specificate dalla regolare
