border=0

Algoritmyske Turing Machine

De Turing-masine bestiet út trije dielen: in tape, in lês-skriuwer en in logikaasje (7.1).

It tape docht as eksterne ûnthâld; It wurdt beskôge as ûnbegryplik (ûneinich) - dit al toant dat de Turing-masine in model-apparaat is, om't gjin echte apparaat in ûnthâld fan unfinigensgrutte hawwe kin.

As yn 'e postmasine is it tape ferdield yn getal selden, lykwols, yn' e Turing-masine is de holle stasjon, en de tape bewegt relatyf dêrby nei rjochts of lofts. In oar ferskil is dat it net wurket yn 'e binêre, mar yn guon arbitrêre finite alfabet A = {Δ, mar 1 , ... mar n } - dit alfabet wurdt eksterne neamd . Yn dat is in spesjaal karakter - Δ, neamd it lege teken - it ferstjoeren nei in sel selektearret it teken dat earder dêr wie en de sel selde lit. Allinnich ien karakter kin skreaun wurde yn elke sellen fan 'e tape. De ynformaasje dy't op 'e tape opslein is wurdt beskreaun troch in finitale folchoarder fan eksterne alfabetyske letters, oars as it lege karakter.

De holle leit altyd boppe ien fan 'e tapezellen. It wurk docht yn stappen (stappen). It systeem fan kommando's troch it holle útfierd is hiel ienfâldich: by elke kloksezyklus ferplakt it teken yn 'e kontrolearre sellen in i mei in teken a j . Tagelyk kombinaasjes binne mooglik:

J = i - dit betsjut dat it teken yn 'e kontrolearre sellen net feroare hat;

I ≠ 0, j = 0 betsjuttet dat it teken yn de sel selektearre is troch in lege, d. wurdt wiske;

I = 0, j ≠ 0 betsjuttet dat it lege karakter is ferfongen troch in net-lege (mei nûmer j yn it alfabet), d. De mark is ynset;

· Ikj ≠ 0 komt oerien mei de ferfanging fan ien karakter troch in oar.

Sa makket de Turing-masine in systeem fan ienfâldige ynformaasjeferwurkingsbehearders, dy't besprutsen binne yn paragraaf 7.3.1. Dit systeem fan ferwurkingsbehearders wurdt ek oanfolle troch in heul ienfâldige systeem fan kommando's foar it ferpleatsen fan de tape: nei de sel foar links, nei de sel foar rjochts, en op it plak te bliuwen, d. it adres fan 'e kontrolearre sel as resultaat fan de kommando-útfiering kin wizigje op 1 of bliuw net feroare. Hoewol de tape ferdwynt, wurdt it normaal beskôge as in haadverschjitting yn relaasje ta de sesje dy't sjoen wurdt - dêrom is it kommando om de tape nei lofts te ferpleatsen te sjen troch R ("Rjochts"), skeakelje nei rjochts - L ("Lofts"), en gjin skeakel - S ("Stop"). Yn Fan no ôf sprekke wy oer de skift fan 'e kop en beskôgje R, L en S as kommando's fan har beweging. De elemintêre karakter fan dizze kommando's betsjuttet dat, as it nedich is om te ferwizen nei de ynhâld fan in bepaalde sel, wurdt allinich trochskreaun troch in keten fan yndividuele fersiken per sel. Natuurlijk ferlit dizze dan it ferwurkjen proses, mar it makket it te meitsjen sûnder sel nummering en it gebrûk fan gotoadreskommando's, d. Reduzet it oantal echte elemintêre stappen, dy't wichtich is yn teoretyske terminen.

De ferwurking fan ynformaasje en útjaan fan kommando's om de mark te skriuwen, lykas ek de tapeverschak yn 'e Turing-masine, wurdt útfierd troch in logikaasje (LU). It kin wêze yn ien fan 'e steaten dy't in definitive set foarmje en wurde oantsjutten mei Q = { q 1 ... q m , z } , fierder, de steat z oerienkomt mei it taak fan it wurk, en q 1 is de earste (earste) ien. Q yn 'e mande mei de tekens R, L, S foarmje it ynderlike alfabet fan' e masine. De LU hat twa ynfierkanals ( i , q i ) en trije útfieringskanalen ( in i + 1 , q i + 1, D i +1 ) (sjoch figuer):

It skema moat as folgjende begrepen wurde: by it fysyk is in teken fan 'e no selektearre selle ( in i ) op ien input fan' e LU stjoerd , en nei in oare ynfier, in teken wêrby't de steat fan 'e LU yn it momint ( q i ). Ofhinklik fan 'e kombinaasje fan tekens dy't ûntfangen binne ( in i , q i ) en de besteande ferwurkingsregels, ûntfong de LU en stjoert in nij karakter (D i + 1 ) nei de bewarre selle op it earste útfier kanaal ( in i +1 ). fan R, L en S ), en jout ek de kommando om it folgjende steuring teken te neamen (q i + 1 ). Sa wurdt it elemintêre stap (fyts) fan de Turing-masine-operaasje sa folge: de kop lêst in karakter út 'e bewarre sel, en, ôfhinklik fan syn steat en it karakter lêzen, útfiert in kommando dy't oanjulet hokker karakter skriuwt (of ferwiderje) en hokker beweging om út te fieren . Yn dit gefal giet de kop nei in nije state. It skema fan it funksjonearjen fan sa'n masine is yn 'e ôfbylding werjûn. 7.2.

Dit skema reflektet de ôfdieling fan oantinken yn eksterne en yntern. De bûtenkant wurdt fertsjintwurdige, lykas neamd, yn 'e foarm fan in endless lip - it is bedoeld om ynformaasje te bewarjen dy't kodearre yn' e symboalen fan it bûtenlânske alfabet. It ynterne ûnthâld is fertsjintwurdige troch twa sellen foar it bewarjen fan it kommende kommando yn 'e aktive kloksyklus: de folgjende stân ( q i + 1 ) wurdt nei Q ferstjoerd en it skermbefeiliging ( D i +1 ) wurdt bewarre yn D. Fan Q op 'e feedback line q i + 1 yntrodusearret de LU, en fan D komt it kommando oan by de actuator, dy't, as nedich, de tape ien posysje nei rjochts of links ferpleatst.

De algemiene regel wêrmei't de Turing masine wurket kin fertsjintwurdige wurde troch de folgjende yngong: q i a jq i ' a j ' D k , d. nei it oersjen fan it karakter in j mei de kop yn 'e state in i , it karakter in j ' is yn 'e sel foarskreaun, de kop giet nei de state q i ', en de band makket de beweging D k . Foar elke kombinaasje q i a j, is der ien iennichste konverzje regel (der binne gjin regels allinich foar z , om't, ien kear yn dizze steat de masine stopet). Dit betsjut dat de logyske blok in funksje ymplemintearret dy't elk paar yntaksjes jildt: q i a j nei ien en iennichste triple output q i ' a j ' D k - it wurdt de logyske funksje fan 'e masine neamd en wurdt normaal fertsjintwurdearre as in tabel (funksjoneel diagram fan' e masine) kolommen wêrfan troch symboalen fan steaten en rigen troch symboalen fan in eksterne alfabet neamd wurde. As de karakteren fan it eksterne alfabet n binne, en it oantal steat fan 'e dL is dan, fansels, it totale tal transformationregelings net nedich wêze .

In spesifike Turing-masine wurdt oantsjutte troch it lizzen fan eleminten fan 'e sets A en Q , en ek troch de logyske funksje dy't de LU ymplet, d. set fan transformaasjeregels. It is dúdlik dat der in protte ferskillende sets fan A, Q en logyske funksjes, i. en Turingmasines binne ek in protte.

Foar it besprekken fan it funksjonearjen fan 'e Turing-masine, meitsje wy in oare konsept.

De totaliteit fan 'e tastannen fan alle tapezellen, de steat fan' e LU en de posysje fan 'e kop wurdt de masine-konfiguraasje neamd.

De konfiguraasje kin skreaun wurde as folgjend: Δ a 1 q i a j ... en k Δ dat betsjut dat seksyon j is yn in wurd fan k teken besjoen en it kontrôleapparat is yn 'e state q i . It is dúdlik dat de konfiguraasje fan 'e masine elke oantal karakters befetsje yn it eksterne alfabet en mar ien karakter yn it ynterne. Faak wurdt de konfiguraasje as α 1 q i α 2 skreaun , wêrby't α 1 it wurd op 'e pân nei links fan' e kop is, α 2 is it wurd op 'e bape oan' e rjochterkant fan 'e kop, ynklusyf it teken om te observearjen. Om links fan α 1 en nei rjochts fan α 2 is it lint leech. De konfiguraasje is yn fig. 7.1, kin as folgjend skreaun wurde: a 1 Δ a 2 Δ qa 3 a 4 a k , yn fig. 7.2. - 1 q 1111.

Foar it begjin fan 'e wurken is it oarspronklike wurd α fan finiten>A skreaun op in lege tape ; de holle leit boppe it earste karakter fan it wurd α, de LL wurdt oerbrocht nei de steat q 1 (d. de earste konfiguraasje is q 1 α ). Om't allinich in transformaasje-regel yn elke konfiguraasje ynfierd wurdt, bepale de earste konfiguraasje ienige opfolgjende masine-operaasje, d. de folsleine ôfdieling fan konfiguraasjes oant it ôfsluten fan wurk.

Ofhinklik fan 'e earste konfiguraasje binne twa mooglik ûntwikkelings mooglik:

Nei it finite oantal sikten stopet de masine op in stopbehear; wylst op 'e tape de lêste konfiguraasje is dy't oerienkomt mei de útfier ynformaasje;

Stop stopet net.

Yn it earste gefal sizze se dat masine oanwêzich is foar de begjinnende ynformaasje, yn 't twadde kear - net. De folsleine ynstelling fan konfiguraasjes dêr't de masine it resultaat biedt, foarmje in klasse fan taken. Fansels, in Turing-masine te brûken foar in probleem dat net yn 'e klasse is te lêzen is betsjuttingen. Oan 'e oare kant is yn in soad gefallen it mooglik om de klasse fan taken út te wreidzjen troch in oare Turingmasine te meitsjen. De fraach is ûntstien: is it mooglik om sokke universele masines op te bouwen (op syn minst op in teoretysk nivo) dy't alle problemen oplossje soe? Hjirby naam se de fraach fan algoritmyske lienens, dy't letter ûndersocht wurde.





Sjoch ek:

Closed and open systems

Foarbyld 5.3

Foarbyld A.1

Betingske entropy

Block binêre kodearring

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ edudocs.fun