Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
* páska: Páska Turingovho stroja slúži ako primárne ukladanie a vstupné/výstupné médium. Vstupná sekvencia je spočiatku zapísaná na pásku. Zvyšok pásky (potenciálne nekonečná na dĺžku) je pôvodne vyplnená slepými symbolmi.
* hlava na čítanie/zápis: Hlava dokáže prečítať symbol v aktuálnej polohe na páske, napísať nový symbol na pásku v jeho aktuálnej polohe a presunúť jednu polohu doľava alebo doprava.
* Štátny register: To drží súčasný stav Turingovho stroja. Stav predstavuje „pamäť“ stroja, čo doteraz urobil.
* Funkcia prechodu (alebo tabuľka): Toto je srdce logiky Turingovho stroja. Diktuje správanie stroja na základe jeho súčasného stavu a symbolu, ktorý je v súčasnosti pod hlavou čítania/zápisu. Funkcia prechodu sa zvyčajne vyjadruje ako súbor pravidiel alebo tabuľka, ktorá mapuje (aktuálny stav, aktuálny symbol) na (nový stav, nový symbol na písanie, smer k pohybu).
Ako to funguje-krok za krokom:
1. Inicializácia:
* Vstupná sekvencia je zapísaná na pásku.
* Hlava čítania/zápisu je umiestnená na začiatku vstupnej sekvencie (zvyčajne symbol v ľavej strane).
* Stroj začína v určenej časti „Štart“.
2. iterácia: Turingový stroj opakovane vykonáva nasledujúce kroky:
* čítaj: Hlava čítania/zápisu číta symbol v aktuálnej polohe na páske.
* Vyhľadávanie: Stroj vyhľadá pár (aktuálny stav, aktuálny symbol) pár vo svojej funkcii prechodu. Funkcia prechodu poskytuje tri informácie:
* nový stav: Stroj prechádza do nového stavu.
* nový symbol: Stroj zapíše na pásku nový symbol v aktuálnej polohe (prepísanie starého symbolu). Môže to byť rovnaké ako starý symbol, ktorý ho skutočne nezmení.
* Smer: Stroj posúva hlavu čítania/zápisu jednu polohu doľava alebo doprava na páske.
* Aktualizácia: Stroj aktualizuje svoj štátny register v novom štáte. Potom posúva hlavu čítania/zápisu podľa zadaného smeru a zapisuje nový symbol.
3. Zastavenie (prijatie/odmietnutie):
* Stroj pokračuje v opakovaní, až kým sa nestane jedna z dvoch vecí:
* Stav zastavenia: Funkcia prechodu môže špecifikovať „stav zastavenia“. Keď stroj vstúpi do zastavovacieho stavu, prestane sa vykonávať. Zastavovacie štáty môžu byť „prijímajúce“ alebo „odmietnutie“ v závislosti od požadovaného výsledku.
* Žiadny prechod: Nemusí existovať žiadny definovaný prechod pre súčasnú kombináciu (stav, symbol). To tiež spôsobí zastaviť stroj.
Manipulácia s rôznymi vstupnými sekvenciami:
Turingov stroj efektívne * spracováva * Vstupnú sekvenciu založenú na svojej prechodnej funkcii. Funkcia prechodu je navrhnutá tak, aby vykonáva určitú konkrétnu úlohu, napríklad:
* Rozpoznanie jazyka: Určenie, či vstupná sekvencia patrí do preddefinovaného jazyka. Napríklad by mohla skontrolovať, či reťazec obsahuje rovnaký počet '0 a' 1. Stroj by sa zastavil v akceptovanom stave, ak reťazec patrí do jazyka a odmietajúcemu stavu inak.
* Transformácia vstupu: Konverzia vstupnej sekvencie na inú výstupnú sekvenciu. Napríklad by mohla vykonávať sčítanie, odčítanie alebo logické operácie. Výstup by zostal na páske, keď sa stroj zastaví.
* triedenie: Usporiadanie vstupnej sekvencie v konkrétnom poradí.
* simulácia: Simulujte správanie iného Turingovho stroja alebo výpočtového systému.
Príklad (zjednodušené rozpoznávanie jazyka):
Povedzme, že chceme, aby Turingov stroj rozpoznal jazyk všetkých reťazcov pozostávajúcich iba z „1. Funkcia prechodu môže vyzerať takto:
* State A (Start State):
* Ak znie '1', napíšte '1', presuňte sa doprava, prejdite do štátu A.
* Ak sa prečíta prázdne ('b'), napíšte 'b', presuňte sa doprava, prejdite do stavu.
* Ak znie '0', napíšte '0', presuňte sa doprava, prejdite do štátneho odmietnutia.
* State akceptujte: Zastavte a prijmite.
* Stav odmietnutie: Zastaviť a odmietnuť.
Ak je vstup „111“, stroj by:
1. Začnite v stave A, prečítajte si „1“, napíšte „1“, presuňte sa doprava, choďte do štátu A.
2. Začnite v stave A, prečítajte si „1“, napíšte „1“, presuňte sa doprava, choďte do štátu A.
3. Začnite v stave A, prečítajte si „1“, napíšte „1“, presuňte sa doprava, choďte do štátu A.
4. Začnite v stave A, prečítajte si „b“, napíšte „b“, presuňte sa doprava, prejdite do štátu Prijať.
5. Zastavte sa v štáte.
Ak je vstup „101“, stroj by:
1. Začnite v stave A, prečítajte si „1“, napíšte „1“, presuňte sa doprava, choďte do štátu A.
2. Začnite v stave A, prečítajte si „0“, napíšte '0', presuňte sa doprava, prejdite do štátneho odmietnutia.
3. Zastavte sa v štátnom odmietnutí.
Kľúčové koncepty:
* Determinizmus: Najčastejšie sú Turing stroje deterministické. To znamená, že pre každý (stav, symbol) pár je iba jeden definovaný prechod. Neterministické Turing stroje (NDTMS) umožňujú viac prechodov, ale sú teoreticky ekvivalentné deterministickým Turingovým strojom.
* Power: Turingov stroj je výkonným teoretickým modelom výpočtu. Môže simulovať akýkoľvek algoritmus, ktorý je možné vykonať na digitálnom počítači.
* Obmedzenia: Aj keď sú teoreticky výkonné, Turing Stroje sú veľmi nízke a únavné priamo programovať. Praktickejšie programovacie jazyky a architektúry abstraktujú podrobnosti o prechodoch pásky, hlavy a štátu. Pochopenie základného modelu Turing Machine však pomáha porozumieť základným obmedzeniam výpočtu.
Stručne povedané, Turingov stroj spracováva rôzne konfigurácie sekvencií systematickým čítaním, písaním a pohybom na páske, riadené jeho prechodnou funkciou a štátnym registrom. Funkcia prechodu je starostlivo navrhnutá tak, aby vykonala špecifický výpočet vstupnej sekvencie, čo umožňuje stroju prijímať, odmietnuť alebo transformovať vstup na základe jeho charakteristík.