Turingi masin Vaata ka | Kirjandus | Välislingid | NavigeerimismenüüOn Computable Numbers, With an Application to the EntscheidungsproblemTuring MachineTeaduse helisõnastik: Turingi masinTuringi masinad
LoogikaFilosoofia
Alan Turingi1937abstraktne arvutiarvutatavuse
(function()var node=document.getElementById("mw-dismissablenotice-anonplace");if(node)node.outerHTML="u003Cdiv class="mw-dismissable-notice"u003Eu003Cdiv class="mw-dismissable-notice-close"u003E[u003Ca tabindex="0" role="button"u003Epeidau003C/au003E]u003C/divu003Eu003Cdiv class="mw-dismissable-notice-body"u003Eu003Cdiv id="localNotice" lang="et" dir="ltr"u003Eu003Cpu003Eu003Cbigu003EOsale artiklivõistlusel u003Ca href="/wiki/Vikipeedia:Wikimedia_CEE_Spring_2019" title="Vikipeedia:Wikimedia CEE Spring 2019"u003EKesk- ja Ida-Euroopa kevadu003C/au003E!u003C/bigu003Enu003C/pu003Eu003C/divu003Eu003C/divu003Eu003C/divu003E";());
Turingi masin
Jump to navigation
Jump to search
Turingi masin [tj'uuringi] on Alan Turingi 1937. aastal kirjeldatud lihtne abstraktne arvuti, mida kasutatakse arvutatavuse ja selle piiride uurimiseks.
Turingi masin koosneb mõlemas suunas lõpmata pikast lindist, mis on jagatud ühesugusteks pesadeks. Iga pesa võib olla kahes asendis: tähisega või tähiseta. Turingi masinal on viis võimalikku operatsiooni: teha samm vasakule, teha samm paremale, kirjutada pessa tähis, kustutada pesast tähis ja kontrollida, kas pesas on tähis.
Universaalse Turingi masina korral määrab lint ära ka teise Turingi masina. Algselt on tähised lõplikus hulgas pesades, ülejäänutes on tühikud. Sisemälu on igal ajahetkel mingis konkreetses seisundis ja taoliste seisundite hulk on lõplik.
Masina tegevusi juhtivad reeglid on deterministlikud ja on defineeritud seisunditabelis. Iga seisundi ja iga lindil oleva tähise kohta on tabelis kirje masinapoolse tegevuse ja järgmise seisundi kohta.
Kuna masina seisundite ja lindil olevate tähiste arv on lõplik, siis on ka tabel lõpliku suurusega ja seda saab hoida lindil. Eksisteerib universaalne Turingi masin Mudisplaystyle M_u, mis on võimeline jäljendama iga Turingi masinat, sealhulgas iseennast. Kui masina Mdisplaystyle M seisunditabel on kirjutatud Mudisplaystyle M_u lindile, siis teostab universaalne masin Mudisplaystyle M_u samu operatsioone mis Mdisplaystyle M. Universaalne masin teeb seda, leides masina Mdisplaystyle M seisunditabeli järgi selle tegevused iga võimaliku sisendi korral.
Vaata ka |
- Churchi tees
- Entscheidungsproblem
Kirjandus |
- Palm, Reimo; Prank, Rein 1994. Sissejuhatus matemaatilisse loogikasse. Tartu.
Välislingid |
- Alan Turingi "On Computable Numbers, With an Application to the Entscheidungsproblem"
- Märksõna Turing Machine Stanfordi ülikooli filosoofialeksikonis.
Teaduse helisõnastik: Turingi masin (Leo Mõtus) – ERR Teadus, 14. jaanuar 2010
Härmel Nestra: Turingi masinad
Kategooriad:
- Loogika
- Filosoofia
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.036","walltime":"0.066","ppvisitednodes":"value":45,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":0,"limit":2097152,"templateargumentsize":"value":0,"limit":2097152,"expansiondepth":"value":2,"limit":40,"expensivefunctioncount":"value":0,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":216,"limit":5000000,"entityaccesscount":"value":0,"limit":400,"timingprofile":["100.00% 0.000 1 -total"],"cachereport":"origin":"mw1313","timestamp":"20190401132424","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"Turingi masin","url":"https://et.wikipedia.org/wiki/Turingi_masin","sameAs":"http://www.wikidata.org/entity/Q163310","mainEntity":"http://www.wikidata.org/entity/Q163310","author":"@type":"Organization","name":"Wikimedia projektide kaastu00f6u00f6lised","publisher":"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2004-10-15T17:18:00Z","dateModified":"2016-03-10T22:55:09Z"(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":130,"wgHostname":"mw1326"););
