Guida alle Macchine di Turing

tramite: O2O
Difficoltà: media
14

Introduzione

Le macchine di turing consento esattamente di eseguire degli algoritmi in modo astratto. Queste precise macchine comprendono delle regole ben precise, le quali però risultano essere piuttosto semplici. Proprio per questo motivo, potrete tentare di capire da soli il loro esatto funzionamento, in modo tale da non dovervi rivolgere ad un professore di matematica, risparmiando in questo modo grosse somme del vostro prezioso denaro. A questo punto, non vi rimane che continuare a leggere con estrema attenzione le utili informazioni riportate nei successivi passi di questa interessante guida, in modo da comprendere la guida alle Macchine di Turing.

24

Sistema di elementi:

Innanzitutto, dovete sapere che una Macchina di Turing è un sistema di uno specifico numero di elementi abbastanza variegati tra loro. Adesso, supponete di avere la seguente struttura:
- un insieme di stati "S" costituito da "s0" (definito come iniziale per convenzione), "s1", "s2", "s3" ed "s4";
- un insieme degli stati finali "F" (sottoinsieme di "S"), raggiunti i quali l'applicazione delle regole della Macchina di Turing si conclude;
- un insieme di simboli del nastro "N", che potrebbe ricomprendere i simboli "0", "1", "A" e "B";
- un insieme dei simboli d'input "I" (sottoinsieme di "N").

34

Regole:

Dopodichè, bisogna tenere in considerazione le regole accennate nel passaggio precedente della seguente guida, che rappresentano il reale "motore" della Macchina di Turing e manipolano le differenti entità formali finora elencate, con l'obiettivo di rendere dinamico il processo d'attivazione e correlato il funzionamento della stessa Macchina di Turing. Naturalmente, queste regole descrivono concretamente, seppure in una maniera formale, il comportamento algoritmico di una Macchina di Turing: pertanto, provate a descriverle considerando la struttura che è stata precisamente descritta precedentemente.

Continua la lettura
44

Stato iniziale:

Partendo esattamente dallo stato iniziale "s0" (scelto convenzionalmente), la Macchina di Turing deve leggere il simbolo corrente del nastro, raggiungere un determinato stato di arrivo, sostituire sul nastro "A" questo simbolo corrente con un altro simbolo (sempre appartenente all'insieme "N") e poi spostarsi a destra o a sinistra sul medesimo nastro. L'applicazione delle regole di una Macchina di Turing viene reiterata, finché lo stato corrente (raggiunto gradualmente nel tempo d'esecuzione dell'algoritmo implicito) non sarà uno di quelli finali, ovvero appartenenti al sottoinsieme di "S".

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Superiori

Come calcolare l'ampiezza degli angoli di un quadrilatero

La geometria piana tratta delle figure geometriche nel piano: assumono importanza i concetti di lunghezza, angolo e area che molti teoremi mettono in relazione. In particolare, la trigonometria studia le relazioni tra angoli e lunghezze. Tuttavia, la...
Superiori

Come determinare la frontiera di un insieme

Nella matematica, in particolare per quanto riguarda la branca della "topologia", è abbastanza comune imbattersi nel concetto di "insieme": in particolare, esso rappresenta uno spazio che può essere aperto (se ci si può spostare da ciascun punto dell'insieme...
Università e Master

Teorema di Heine-Borel: dimostrazione

Il Teorema di Heine-Borel afferma che un sottospazio di R^n (con la solita topologia) è compatto se e solo se è chiuso e limitato. Tale teorema può essere dimostrato mediante quello di Bolzano-Weierstrass. Inoltre, in chiave moderna è certamente possibile...
Università e Master

Come dimostrare il teorema della permanenza del segno

Durante gli studi relativi ad una tipologia di specie analitica, si inserisce il cosiddetto teorema della permanenza del segno. Tale applicazione moderatamente complessa, serve per dimostrare la veridicità di una funzione, che ha limite denominato mediante...
Università e Master

Come dimostrare il Teorema di Cantor

Il Teorema di Cantor è un risultato di notevole rilievo nell'ambito della Teoria degli Insiemi che riguarda il rapporto in termini di equipotenza tra un insieme S - sia esso finito o infinito - ed il suo insieme delle parti P (S). Tale risultato è evidente...
Università e Master

Come calcolare la distribuzione marginale

All'interno delle teorie di probabilità e di statistica, la distribuzione marginale è un sottoinsieme di una collezione di variabili causali la cui distribuzione di probabilità delle variabili vengono contenute all'interno del sottoinsieme stesso....
Elementari e Medie

Appunti sugli insiemi

In matematica uno dei primi argomenti che si affrontano a scuola è sicuramente quello degli insiemi. Si tratta di qualcosa di molto semplice, sia teoricamente che in pratica. Essendo uno dei concetti più primitivi della matematica, il significato di...
Superiori

Come determinare il sottospazio generato dai vettori

Imparare ed apprendere nuovi concetti matematici non è affatto semplice e, a volte, risulta necessario un ripasso. Succede spesso che alcune teorie vengano solo accennate, lasciando molti dubbi a chi ha il compito di studiarle per bene. Un concetto abbastanza...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.