Tjūringa mašīna ir šādu objektu kolekcija

• 1) ārējais alfabēts A=(a 0 , a 1 , …, a n );
• 2) iekšējais alfabēts Q=(q 1 , q 2 ,…, q m ) - stāvokļu kopa;
• 3) vadības rakstzīmju kopa (P, L, S)
• 4) bezgalīga lente abos virzienos, sadalīta šūnās, no kurām katrā var būt tikai viena rakstzīme no alfabēta A jebkurā diskrētā laikā;
• 5) vadības ierīce, kas spēj atrasties vienā no daudzajiem stāvokļiem

Tukšas šūnas simbols ir ārējā alfabēta burts 0 .

Starp stāvokļiem izšķir sākuma q 1, kurā iekārta sāk darboties, un beigu (vai apstāšanās stāvokli) q 0, kad iekārta apstājas.

Vadības ierīce var pārvietoties pa kreisi un pa labi pa lenti, nolasīt un ierakstīt lentes šūnās A alfabēta rakstzīmes. Vadības ierīce darbojas saskaņā ar komandām, kurām ir šāda forma

q i a j > a p X q k

Ierakstīšana nozīmē sekojošo: ja vadības ierīce atrodas stāvoklī q i un uzraudzītajā šūnā ir ierakstīts burts a j, tad (1) šūnā j vietā tiek ierakstīts p, (2) iekārta turpina pārskatīt nākamo. labā šūna no tikko skatītās, ja X=P, vai lai skatītu nākamo kreiso šūnu, ja X=L, vai turpinātu skatīt to pašu lentes šūnu, ja X=C, (3) vadības ierīce ievada stāvoklis q k.

Tā kā mašīnas darbību pēc nosacījuma pilnībā nosaka tās stāvoklis q konkrētajā brīdī un tajā brīdī skatāmās šūnas saturs a, tad katrai iespējamai konfigurācijai q i a j ir tieši viens noteikums. Nav noteikumu tikai galīgajam stāvoklim, kurā mašīna apstājas. Tāpēc Tjūringa mašīnas programma ar ārējo alfabētu A=(a0, a1, …, an) un iekšējo alfabētu Q=(q1, q2,…, qm) satur ne vairāk kā m (n+ 1) instrukcijas.

Vārds alfabētā A vai alfabētā Q vai alfabētā A Q ir jebkura atbilstošā alfabēta burtu secība. Ar k-to konfigurāciju mēs domājam iekārtas lentes attēlu ar informāciju, kas uz tā izveidojusies līdz k-tā soļa sākumam (vai vārdu alfabētā A, kas uz lentes uzrakstīts līdz k-tais solis), norādot, kura šūna tiek skatīta šajā solī Un kādā stāvoklī ir automašīna? Jēga ir tikai ierobežotām konfigurācijām, t.i. tās, kurās visas lentes šūnas, iespējams, izņemot ierobežotu skaitu, ir tukšas. Konfigurācija tiek uzskatīta par galīgu, ja mašīnas stāvoklis ir galīgs.

Ja par sākotnējo izvēlas jebkuru Tjūringa mašīnas konfigurāciju, kas nav galīga, tad mašīnas uzdevums ir secīgi (soli pa solim) pārveidot sākotnējo konfigurāciju atbilstoši mašīnas programmai, līdz tiek sasniegta galīgā konfigurācija. Pēc tam Tjūringa mašīnas darbs tiek uzskatīts par pabeigtu, un darba rezultāts ir sasniegtā galīgā konfigurācija.

Teiksim, ka netukšu vārdu b alfabētā A (а 0 ) = (a 1 , ..., a n ) iekārta uztver standarta pozīcijā, ja tas ir ierakstīts lentes secīgās šūnās, visas citas šūnas ir tukšas, un iekārta skenē vistālāk kreisās vai labējās šūnas no tām, kurās ir rakstīts vārds b. Standarta pozīciju sauc par sākotnējo (galīgo), ja mašīna, kas uztver vārdu standarta pozīcijā, atrodas sākuma stāvoklī q 1 (respektīvi, apstāšanās stāvoklī q 0).

Ja vārda b apstrāde noved Tjūringa mašīnu līdz galīgajam stāvoklim, tad tiek teikts, ka tas attiecas uz b, pretējā gadījumā tas neattiecas uz b (mašīna darbojas bezgalīgi)

Apsveriet piemēru:

Dota Tjūringa mašīna ar ārējo alfabētu A \u003d (0, 1) (šeit 0 ir tukšas šūnas simbols), iekšējo stāvokļu alfabēts Q \u003d (q 0, q 1, q 2 ) un ar sekojošu funkcionālā diagramma (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;

Šo programmu var uzrakstīt, izmantojot tabulu

Pirmajā solī darbojas komanda: q 1 0 > 1 Л q 2 (vadības ierīce atrodas q1 stāvoklī, un uzraudzītajā šūnā tiek ierakstīts burts 0, šūnā 0 vietā tiek ierakstīts 1, galva pārvietojas pa kreisi, vadības ierīce pārslēdzas uz q2 stāvokli), in Rezultātā mašīnā tiek izveidota šāda konfigurācija:

Visbeidzot, pēc komandas q 2 0 > 0 P q 0 izpildīšanas tiek izveidota konfigurācija

Šī konfigurācija ir galīga, jo iekārta atrodas apturētā stāvoklī q 0 .

Tādējādi iekārta apstrādā sākotnējo vārdu 110 par vārdu 101.

Iegūto konfigurāciju secību var uzrakstīt īsākā veidā (uzraudzītās šūnas saturs tiek rakstīts pa labi no stāvokļa, kurā iekārta pašlaik atrodas):

11q 1 0 => 1 q 2 11 => 1 q 1 11 => 1 q 2 01 => 10 q 0 1

Tjūringa mašīna ir nekas vairāk kā kaut kāds noteikums (algoritms) alfabēta A Q vārdu pārvēršanai, t.i. konfigurācijas. Tādējādi, lai definētu Tjūringa mašīnu, ir jānorāda tās ārējais un iekšējais alfabēts, programma un jānorāda, kurš no simboliem apzīmē tukšu šūnu un beigu stāvokli.

Tjūringa mašīna ir viens no intriģējošākajiem un aizraujošākajiem 20. gadsimta intelektuālajiem atklājumiem. Tas ir vienkāršs un noderīgs abstrakts skaitļošanas (datora un digitālā) modelis, kas ir pietiekami vispārīgs, lai īstenotu jebkuru datora uzdevumu. Pateicoties vienkāršs apraksts un matemātiskās analīzes veikšana veido teorētiskās informātikas pamatu. Šis pētījums ir veicinājis dziļāku izpratni par digitālajiem datoriem un aprēķiniem, tostarp sapratni, ka ir dažas skaitļošanas problēmas, kuras nevar atrisināt ar vispārēju lietotāju datoriem.

Kas tas ir un kas to izveidoja

Alans Tjūrings centās aprakstīt primitīvāko mehāniskās ierīces modeli, kam būtu tādas pašas pamata iespējas kā datoram. Pirmo reizi Tjūrings mašīnu aprakstīja 1936. gadā "On Computable Numbers with an Application to the Decidability Problem", kas tika publicēts Proceedings of the London Mathematical Society.

Tjūringa mašīna ir skaitļošanas ierīce, kas sastāv no lasīšanas/rakstīšanas galviņas (vai "skenera") ar papīra lenti, kas iet cauri tai. Lente ir sadalīta kvadrātos, no kuriem katrs satur vienu simbolu - "0" vai "1". Mehānisma mērķis ir tas, ka tas darbojas gan kā ieejas un izejas līdzeklis, gan kā darba atmiņa aprēķinu starpposmu rezultātu glabāšanai.

No kā ir izgatavota ierīce?

Katra šāda iekārta sastāv no divām sastāvdaļām:

1. Neierobežots lentes. Tas ir bezgalīgs abos virzienos un ir sadalīts šūnās.
2. Iekārta ir vadāma programma, skenera galva datu lasīšanai un rakstīšanai. Jebkurā brīdī tas var būt vienā no daudzajiem stāvokļiem.

Katra iekārta saista divas galīgas datu sērijas: ievades simbolu alfabēts A = (a0, a1, ..., am) un stāvokļu alfabēts Q = (q0, q1, ..., qp). Stāvokli q0 sauc par pasīvu. Tiek uzskatīts, ka ierīce beidz savu darbu, kad tai atsitas. Stāvokli q1 sauc par sākuma stāvokli – iekārta sāk aprēķinus, atrodoties tajā pašā sākumā. Ievades vārds tiek ievietots lentē pa vienu burtu pēc kārtas katrā pozīcijā. Abās tā pusēs ir tikai tukšas šūnas.

Kā darbojas mehānisms

Tjūringa mašīnai ir būtiska atšķirība no skaitļošanas ierīcēm - tās glabāšanas ierīcei ir bezgalīga lente, savukārt digitālajām ierīcēm šādai ierīcei ir noteikta garuma sloksne. Katru uzdevumu klasi risina tikai viena konstruēta Tjūringa mašīna. Cita veida uzdevumi ietver jauna algoritma rakstīšanu.

Vadības ierīce, atrodoties vienā stāvoklī, var pārvietoties jebkurā virzienā pa lenti. Tas raksta šūnās un nolasa no tām pēdējā alfabēta rakstzīmes. Pārvietošanas laikā tiek piešķirts tukšs elements, kas aizpilda pozīcijas, kas nesatur ievaddatus. Tjūringa mašīnas algoritms nosaka vadības ierīces pārejas noteikumus. Tie iestata šādus parametrus rakstīšanas-lasīšanas galviņai: jaunas rakstzīmes ierakstīšana šūnā, pāreja uz jaunu stāvokli, pārvietošanās pa kaseti pa kreisi vai pa labi.

Kustības īpašības

Tjūringa mašīnai, tāpat kā citām skaitļošanas sistēmām, ir raksturīgas iezīmes, un tās ir līdzīgas algoritmu īpašībām:

1. diskrētums. Digitālā iekārta pāriet uz nākamo soli n+1 tikai pēc tam, kad ir pabeigts iepriekšējais. Katrs pabeigtais solis norāda, kas būs n+1.
2. Skaidrība. Vienai un tai pašai šūnai ierīce veic tikai vienu darbību. Tas ievada rakstzīmi no alfabēta un veic vienu kustību: pa kreisi vai pa labi.
3. Noteiktība. Katra pozīcija mehānismā atbilst vienīgajam dotās shēmas variantam, un katrā posmā darbības un to izpildes secība ir nepārprotama.
4. Efektivitāte. Precīzu rezultātu katram solim nosaka Tjūringa mašīna. Programma izpilda algoritmu un ar ierobežotu skaitu soļu pāriet uz stāvokli q0.
5. Masu raksturs. Katra ierīce ir definēta virs atļautajiem vārdiem, kas iekļauti alfabētā.

Tjūringa mašīnas funkcijas

Risinot algoritmus, bieži vien ir nepieciešama funkcijas ieviešana. Atkarībā no iespējas uzrakstīt ķēdi aprēķinam, funkciju sauc par algoritmiski izšķiramu vai neizšķiramu. Kā naturālu vai racionālu skaitļu kopa, vārdi galīgā alfabētā N mašīnai tiek uzskatīta kopas B secība - vārdi binārā koda alfabēta ietvaros B=(0,1). Arī aprēķina rezultātā tiek ņemta vērā “nenodefinētā” vērtība, kas rodas, kad algoritms “sasalst”. Funkcijas īstenošanai ir svarīgi, lai galīgajā alfabētā būtu formāla valoda un pareizi aprakstu atpazīšanas problēma būtu atrisināma.

Ierīces programmatūra

Tjūringa mehānisma programmas ir sakārtotas tabulās, kurās pirmajā rindā un kolonnā ir ārējā alfabēta simboli un automāta iespējamo iekšējo stāvokļu vērtības - iekšējais alfabēts. Tabulas dati ir komandas, kuras Tjūringa mašīna pieņem. Problēmu risināšana notiek šādi: burts, ko nolasa galva šūnā, virs kuras tā pašlaik atrodas, un automāta galvas iekšējais stāvoklis nosaka, kura no komandām ir jāizpilda. Konkrēti, šāda komanda atrodas ārējā alfabēta un iekšējā alfabēta simbolu krustpunktā, kas atrodas tabulā.

Sastāvdaļas aprēķiniem

Lai izveidotu Tjūringa mašīnu vienas konkrētas problēmas risināšanai, tai ir jādefinē šādi parametri.

ārējais alfabēts. Šī ir noteikta simbolu kopa, ko apzīmē ar zīmi A, kuras veidojošos elementus sauc par burtiem. Vienam no tiem - a0 - jābūt tukšam. Piemēram, Tjūringa ierīces, kas strādā ar bināriem skaitļiem, alfabēts izskatās šādi: A = (0, 1, a0).

Nepārtrauktu burtu-simbolu ķēdi, kas ierakstīta lentē, sauc par vārdu.

Automāts ir ierīce, kas darbojas bez cilvēka iejaukšanās. Tjūringa mašīnā tai ir vairāki dažādi stāvokļi problēmu risināšanai un noteiktos apstākļos tā pārvietojas no vienas pozīcijas uz citu. Šādu pārvadāšanas stāvokļu kopums ir iekšējais alfabēts. Viņam ir burtu apzīmējums formā Q=(q1, q2...). Vienai no šīm pozīcijām - q1 - jābūt sākotnējai, tas ir, tai, kas sāk programmu. Vēl viens nepieciešamais elements ir stāvoklis q0, kas ir gala stāvoklis, tas ir, tas, kas pārtrauc programmu un pārvieto ierīci uz apturēšanas pozīciju.

Pārlēkšanas galds. Šis komponents ir ierīces karietes darbības algoritms atkarībā no iekārtas pašreizējā stāvokļa un nolasāmās rakstzīmes vērtības.

Algoritms automātam

Tjūringa ierīces pārvadāšanu darbības laikā kontrolē programma, kas katrā solī veic šādu darbību secību:

1. Ārējā alfabēta rakstzīmes ierakstīšana pozīcijā, ieskaitot tukšu, aizstājot tajā esošo elementu, ieskaitot tukšu.
2. Pārvietojiet vienu soli pa kreisi vai pa labi.
3. Mainiet savu iekšējo stāvokli.

Tādējādi, rakstot programmas katram rakstzīmju vai pozīciju pārim, ir precīzi jāapraksta trīs parametri: a i - elements no izvēlētā alfabēta A, karietes pārvietošanas virziens ("←" pa kreisi, "→" uz pa labi, "punkts" - nav kustības) un q k - jauns ierīces stāvoklis. Piemēram, komandai 1 "←" q 2 ir nozīme "aizstāt rakstzīmi ar 1, pārvietot karietes galvu pa kreisi par vienu pakāpiena šūnu un pāriet uz stāvokli q 2 ".

Tjūringa mašīna: piemēri

1. piemērs Uzdevums ir izveidot algoritmu, kas pieskaita vienu līdz pēdējam ciparam dotajam ciparam, kas atrodas uz lentes. Ievaddati - vārds - vesela decimālskaitļa cipari, kas ierakstīti lentes secīgās šūnās. Sākotnējā brīdī ierīce atrodas pretī galējam labās puses rakstzīmei - cipara ciparam.

Risinājums. Ja pēdējais cipars ir 9, tad tas jāaizstāj ar 0 un pēc tam jāpievieno viens iepriekšējai rakstzīmei. Programmu šajā gadījumā konkrētai Tjūringa ierīcei var uzrakstīt šādi:

Šeit q 1 ir cipara maiņas stāvoklis, q 0 ir pietura. Ja q 1 automāts fiksē elementu no rindas 0..8, tad to attiecīgi aizstāj ar vienu no 1..9 un pēc tam pārslēdzas uz stāvokli q 0, tas ir, iekārta apstājas. Ja kariete fiksē skaitli 9, tad to aizstāj ar 0, pēc tam pārvietojas pa kreisi, apstājoties stāvoklī q 1 . Šī kustība turpinās, līdz ierīce fiksē ciparu, kas ir mazāks par 9. Ja visas rakstzīmes ir vienādas ar 9, tās tiek aizstātas ar nullēm, augstākā elementa vietā tiks ierakstīts 0, ratiņš pārvietosies pa kreisi un ierakstīs 1, lai tukša šūna. Nākamais solis būs pāreja uz stāvokli q 0 - stop.

2. piemērs Dota virkne simbolu, kas apzīmē atvēršanas un aizvēršanas iekavas. Ir nepieciešams izveidot Tjūringa ierīci, kas noņemtu savstarpēju iekavu pāri, tas ir, elementus, kas sakārtoti rindā - “()”. Piemēram, sākotnējie dati: “) (() (()), atbildei jābūt: “) . . . ((”. Risinājums: mehānisms, atrodoties q 1 , analizē virknes vistālāk kreiso elementu).

Stāvoklis q 1: ja tiek atrasts simbols “(”, pārslēdziet pa labi un pārejiet uz pozīciju q 2; ja ir definēts “a 0”, apstājieties.

q 2. stāvoklis: iekava “(” tiek analizēta, lai noteiktu savienojuma esamību, sakritības gadījumā jāiegūst “)”. Ja elements ir pāris, veiciet ratiņu atgriešanos pa kreisi un dodieties uz q 3 .

Nosakiet q 3: vispirms izdzēsiet rakstzīmi “(” un pēc tam “)” un pārejiet uz q 1 .

Līdz šim mums ir bijis ērti atsaukties uz programmēšanas pieredzi, runājot par algoritmiem, programmām, tulkiem, soļiem utt. Tas ļāva mums ignorēt atsevišķu algoritmu veidošanas detaļas, aizbildinoties, ka lasītājs tos var viegli atjaunot (vai vismaz ticēt, galu galā ne katrs lasītājs savā dzīvē Paskālā rakstīja Paskāla tulku).

Bet dažos gadījumos ar to nepietiek. Ļaujiet, piemēram, pierādīt algoritmisko neatrisināmību kādai problēmai, kuras definīcija neko nesaka par programmām (šajā sadaļā, piemēram, pierādīsim vārda vienlīdzības problēmas neatrisināmību pusgrupās, kuras dod ģeneratori un attiecības) . Parasti tas tiek darīts šādi. Mēs parādām, ka apstāšanās problēma samazinās līdz šai problēmai. Lai to izdarītu, mēs modelējam patvaļīga algoritma darbību saistībā ar aplūkojamo problēmu (ko tas nozīmē, būs redzams tālāk sniegtajā piemērā). Tajā pašā laikā mums ir svarīgi, lai algoritma definīcija būtu pēc iespējas vienkāršāka.

Tātad mūsu plāns ir šāds. Mēs aprakstīsim mašīnu klasi, kuru var definēt diezgan vienkārši (to var izvēlēties daudzos veidos, mēs izmantosim tā sauktās Tjūringa mašīnas), tad deklarēsim, ka uz šādas mašīnas var novērtēt jebkuru izskaitļojamu funkciju, un tad mēs parādīsim, ka jautājumu par Tjūringa mašīnas apturēšanu var reducēt līdz jautājumam par vārdu vienlīdzību pusgrupā.

Vēl viens iemesls, kāpēc vienkārši skaitļošanas modeļi ir svarīgi (to ir daudz dažādi veidi Tjūringa mašīnas, adrešu mašīnas utt.) ir saistīta ar skaitļošanas sarežģītības teoriju, kad mūs interesē izpildes laiks programmas. Bet šis jautājums pārsniedz klasisko algoritmu teoriju.

Tjūringa mašīnas: definīcija

Tjūringa mašīna ir bezgalīga abos virzienos lente, sadalīts kvadrātos ( šūnas). Katra šūna var saturēt kādu rakstzīmi no fiksētas (noteiktai mašīnai) ierobežotas kopas, ko sauc alfabētiskā secībāšo mašīnu. Viens no alfabēta simboliem ir izcelts un tiek saukts par "atstarpi", tiek pieņemts, ka sākotnēji visa lente ir tukša, tas ir, piepildīta ar atstarpēm.

Tjūringa mašīna var mainīt lentes saturu, izmantojot īpašu lasītāju un rakstītāju. galvas, kas pārvietojas pa lenti. Katru brīdi galva atrodas vienā no šūnām. Tjūringa mašīna no galvas saņem informāciju par to, kādu simbolu tā redz, un atkarībā no tā (un no tā iekšējā stāvokļa) izlemj, ko darīt, tas ir, kādu simbolu rakstīt pašreizējā šūnā un kur pēc tam pārvietoties (pa kreisi, pa labi vai palieciet vietā). Tas arī maina iekārtas iekšējo stāvokli (mēs pieņemam, ka iekārtai, izņemot lenti, ir ierobežota atmiņa, tas ir, ierobežots skaits iekšējo stāvokļu). Jāvienojas arī par to, kur sākam un kad pabeidzam darbus.

Tādējādi, lai definētu Tjūringa mašīnu, ir jānorāda šādi objekti:

Pārlēkšanas tabula ir sakārtota šādi: katram pārim ir norādīts trīskāršs. Šeit maiņa ir viens no cipariem -1 (pa kreisi), 0 (vietā) un 1 (pa labi). Tādējādi pārejas tabula ir S x A -> S x A x (-1,0,1) tipa funkcija, kas definēta tiem pāriem, kuros stāvoklis nav galīgs.

Atliek aprakstīt Tjūringa mašīnas uzvedību. Katru brīdi ir kāds konfigurācija, kas sastāv no lentes satura (formāli runājot, lentes saturs ir patvaļīgs kartējums Z -> A ), galviņas pašreizējā stāvokļa (dažs vesels skaitlis ) un iekārtas pašreizējā stāvokļa (elements S ). Konfigurācijas pārveidošana par nākamo notiek pēc dabiskiem likumiem: tabulā apskatām, kas jādara konkrētajam stāvoklim un konkrētajam simbolam, tas ir, uzzinām jauno mašīnas stāvokli, mainām simbolu uz norādīto un pēc tam pārvietojiet galvu pa kreisi, pa labi vai atstājiet to vietā. Šajā gadījumā, ja jaunais stāvoklis ir viens no pēdējiem, mašīnas darbība beidzas. Atliek vienoties par to, kā mēs iesniedzam informāciju mašīnas ievadei un kas tiek uzskatīts par tās darba rezultātu. Mēs pieņemsim, ka mašīnas alfabēts papildus atstarpei satur rakstzīmes 0 un 1 (un, iespējams, arī dažas citas rakstzīmes). Iekārtas ievade un izvade būs ierobežotas nulles un vieninieku secības (bināri vārdi). Ievades vārds tiek uzrakstīts uz tukšas lentes, mašīnas galva tiek ievietota tās pirmajā šūnā, iekārta tiek inicializēta un iedarbināta. Ja iekārta apstājas, rezultāts ir binārs vārds, ko var nolasīt, sākot no galvas pozīcijas un virzoties pa labi (līdz parādās rakstzīme, kas nav 0 un 1).

Tādējādi jebkura Tjūringa mašīna definē kādu daļēju funkciju binārajiem vārdiem. Ir dabiski izsaukt visas šādas funkcijas aprēķināms uz Tjūringa mašīnām.

Tjūringa mašīnas: diskusija

Protams, mūsu definīcija satur daudzas konkrētas detaļas, kuras varētu mainīt. Piemēram, lente var būt bezgalīga tikai vienā virzienā. Jūs varat dot mašīnai divas lentes. Mēs varam pieņemt, ka iekārta var vai nu uzrakstīt jaunu rakstzīmi, vai pārvietoties, bet ne abus. Ir iespējams ierobežot alfabētu, pieņemot, teiksim, ka tajā jābūt tieši 10 rakstzīmēm. Jūs varat pieprasīt, lai beigās nekas nebūtu uz lentes, izņemot darba rezultātu (pārējām šūnām jābūt tukšām). Visas šīs un daudzas citas izmaiņas nemaina Tjūringa mašīnās aprēķināmo funkciju klasi. Protams, nav arī nekaitīgu izmaiņu. Piemēram, ja jūs aizliedzat automašīnai pārvietoties pa kreisi, tad tas radikāli mainīs situāciju pēc būtības, lente kļūs bezjēdzīga, jo vairs nebūs iespējams atgriezties pie vecajiem ierakstiem.

Kā saprast, kuras izmaiņas ir nekaitīgas un kuras nē? Acīmredzot šeit ir nepieciešama vismaz neliela praktiskā programmēšanas pieredze Tjūringa mašīnās. Pēc tam jau var iedomāties mašīnas iespējas, neizrakstot programmas pilnībā, bet vadoties tikai pēc aptuvena apraksta. Kā piemēru aprakstīsim mašīnu, kas divkāršo ievades vārdu (izveido vārdu XX, ja ievade bija vārds X).

Ja iekārta redz atstarpi (ievades vārds ir tukšs), tā aizveras. Ja nē, tas atceras pašreizējo rakstzīmi un ieliek atzīmi (alfabētā papildus rakstzīmēm 0 un 1 būs arī to "atzīmētie varianti" un ). Pēc tam viņa pāriet pa labi uz tukšu šūnu, pēc tam viņa tur ieraksta atcerētā varoņa kopiju. Tad viņa pārvietojas pa kreisi līdz atzīmei; apglabājot sevi zīmē, atkāpjas un atceras nākamo varoni un tā tālāk, līdz viņš nokopē visu vārdu.

Ar zināmu pieredzi aiz visām šīm frāzēm var redzēt konkrētus Tjūringa mašīnas programmas elementus. Piemēram, vārdi "iegaumēt rakstzīmi un pārvietoties pa labi" nozīmē, ka ir divas stāvokļu grupas: viena situācijai, kad tiek saglabāta nulle, otra, kad tiek saglabāta viena, un katrā grupā kustība pa labi. ir ieprogrammēts uz pirmo tukšo šūnu.

Ar nedaudz vairāk pieredzes jūs varat saprast, ka šajā aprakstā ir kļūda, jo netiek nodrošināts apturēšanas mehānisms, kad tiek kopēts viss vārds, jo rakstzīmju kopijas neatšķiras no sākotnējā vārda rakstzīmēm. Ir arī skaidrs, kā labot kļūdu, ir nepieciešams rakstīt speciālās rakstzīmes un kā kopijas, un pēdējā posmā noņemt visas atzīmes.

77 . Parādiet, ka apgrieztā funkcija, kas apgriež vārdu atpakaļ, ir aprēķināma Tjūringa mašīnā.

Vēl viens neformālas argumentācijas piemērs: paskaidrosim, kāpēc nevar izmantot papildu rakstzīmes, izņemot 0 , 1 un tukšo rakstzīmi. Lai ir mašīna ar lielu N rakstzīmju alfabētu. Būvēsim jaunu mašīnu, kas simulēs vecās darbību, bet katra vecā šūna atbildīs jaunās k šūnu blokam. Bloka izmērs (skaitlis k) tiks fiksēts tā, lai bloka iekšpusē būtu iespējams iekodēt visas lielā alfabēta rakstzīmes ar nullēm un vieniniekiem. Sākotnējās rakstzīmes 0 , 1 un tukšas tiks kodētas kā 0, kam seko (k-1) tukšas rakstzīmes, 1, kam seko (k-1) tukšas rakstzīmes, un k tukšu rakstzīmju grupa. Vispirms jāievada vārda burti jāpārvieto uz attālumu k, ko var izdarīt bez papildu rakstzīmēm (sasniedzot pēdējo burtu, pārvietot to prom, pēc tam sasniedzot nākamo, pārvietot to un pēdējo utt. ieslēgts); tikai jāsaprot, ka vārda beigas var identificēt kā pozīciju, kam seko vairāk nekā k tukšas rakstzīmes. Ir skaidrs, ka šajā procesā mums atmiņā jāsaglabā ierobežots informācijas apjoms, tāpēc tas ir iespējams. Pēc tam jau ir iespējams soli pa solim simulēt oriģinālās mašīnas darbību, un arī tam pietiek ar ierobežotu atmiņu (e ierobežotu stāvokļu skaitu), jo tikai neliela simulētās mašīnas galvas apkārtne. mums ir svarīgi. Visbeidzot, mums ir jāsaspiež rezultāts atpakaļ.

Diskusijas noslēgumā mēs piedāvājam iepriekš apsolīto argumentu, ka jebkura aprēķināma funkcija ir aprēķināma Tjūringa mašīnā. Lai ir funkcija, ko cilvēks var aprēķināt. Tajā pašā laikā viņam, protams, ir jāizmanto zīmulis un papīrs, jo informācijas apjoms ka viņš var paturēt "savā prātā" ir ierobežots. Mēs pieņemsim, ka viņš raksta uz atsevišķām papīra lapām. Papildus pašreizējai lapai labajā pusē ir papīra kaudze un kreisajā pusē ir kaudze; jūs varat ievietot pašreizējo lapu jebkurā no tām, pabeidzot darbu ar to, un paņemt nākamo no citas kaudzes. Vīrietim ir zīmulis un dzēšgumija. Tā kā ļoti mazi burti nav redzami, lapas skaidri atšķiramo stāvokļu skaits ir ierobežots, un mēs varam pieņemt, ka katru brīdi uz lapas tiek uzrakstīts viens burts no kāda galīga (kaut arī ļoti liela) alfabēta. Cilvēkam ir arī ierobežota atmiņa, tātad viņa stāvoklis ir kādas ierobežotas kopas elements. Tajā pašā laikā var sastādīt kādu tabulu, kurā rakstīts, kā beigsies viņa darbs uz lapas ar doto saturu, sācies dotajā stāvoklī (kas būs uz lapas, kādā stāvoklī būs cilvēks un no kura iepakojuma tiks ņemta nākamā lapa). Tagad jau ir skaidrs, ka cilvēka darbības vienkārši atbilst Tjūringa mašīnas darbam ar lielu (bet ierobežotu) alfabētu un lielu (bet ierobežotu) iekšējo stāvokļu skaitu.

simulators universāla izpildītāja izpētei

Kas tas ir?

Tjūringa mašīnas simulators ir universāla izpildītāja (abstraktā datora) apmācības modelis, ko 1936. gadā ierosināja A. Tjūrings, lai precizētu algoritma jēdzienu. Saskaņā ar Tjūringa tēzi jebkuru algoritmu var uzrakstīt kā programmu Tjūringa mašīnai. Ir pierādīts, ka Tjūringa mašīna pēc savām iespējām ir līdzvērtīga Post mašīnai un parastajiem Markova algoritmiem.

Tjūringa mašīna sastāv no karietes (lasīšanas un rakstīšanas galviņām) un bezgalīgas lentes, kas sadalīta šūnās. Katrā lentes šūnā var būt rakstzīme no kāda alfabēta A=(a 0 ,a 1 ,…,a N ) . Jebkurš alfabēts satur atstarpes simbolu, kas tiek apzīmēts kā 0 vai Λ. Ievadot komandas, atstarpe tiek aizstāta ar pasvītrojumu "_".

Tjūringa mašīna ir automāts, kuru vada galds. Tabulas rindas atbilst izvēlētā alfabēta A simboliem, bet kolonnas atbilst automāta stāvokļiem Q=(q 0 ,q 1 ,…,q M ) . Darbības sākumā Tjūringa mašīna atrodas stāvoklī q 1 . Stāvoklis q 0 ir gala stāvoklis: tajā nokļuvis, automāts beidz savu darbu.

Katrā tabulas šūnā, kas atbilst kādam simbolam a i un kādam stāvoklim q j , ir komanda, kas sastāv no trim daļām:

1. rakstzīme no alfabēta A ;
2. pārvietot virzienu: > (pa labi),
3. jaunas mašīnas stāvoklis

Jaunumi

1. Falina I.N. Tēma "Tjūringa mašīna" datorzinātņu skolas kursā (inf.1september.ru).
2. Mayer R.V. Pasta un Tjūringa mašīnas (komp-model.narod.ru).
3. Piļščikovs V.N., Abramovs V.G., Vylitok A.A., Hot I.V. Tjūringa mašīna un Markova algoritmi. Problēmu risināšana, Maskava: Maskavas Valsts universitāte, 2006.
4. Bekmens I.N. Datorzinātne. 7. lekcija. Algoritmi (profbeckman.narod.ru)
5. Solovjovs A. Diskrētā matemātika bez formulām (lib.rus.ec)
6. Eršovs S.S. Algoritmu teorijas elementi, Čeļabinska, SUSU izdevniecības centrs, 2009.
7. Varpakhovskis F.L. Algoritmu teorijas elementi, M: Enlightenment, 1970.
8. Vereščagins N.K., Šens A. Aprēķināmās funkcijas, M: MTsNMO, 1999.

Ko ar to darīt?

Programmas augšpusē ir redaktora lauks, kurā varat ievadīt problēmas stāvokli brīvā formā.

Lente tiek pārvietota pa kreisi un pa labi, izmantojot pogas, kas atrodas pa kreisi un pa labi no tās. Veicot dubultklikšķi uz lentes šūnas (vai ar peles labo pogu noklikšķinot uz tās), varat mainīt tās saturu.

Izmantojot izvēlni Lente jūs varat saglabāt lentes stāvokli iekšējā buferī un atjaunot lenti no bufera.

Laukā Alfabēts ir iestatītas izvēlētā alfabēta rakstzīmes. Ievadītajām rakstzīmēm automātiski tiek pievienota atstarpe.

Programma tiek ierakstīta tabulā loga apakšā. Pirmajā kolonnā ir alfabēta rakstzīmes, un tā tiek aizpildīta automātiski. Pirmajā rindā ir uzskaitīti visi iespējamie stāvokļi. Varat pievienot un noņemt tabulas (stāvokļa) kolonnas, izmantojot pogas, kas atrodas virs tabulas.

Ievadot komandu tabulas šūnā, vispirms jāievada jauns varonis, tad pārejas virziens un stāvokļa numurs. Ja rakstzīme ir izlaista, tā pēc noklusējuma nemainās. Ja valsts numurs tiek izlaists, automāta stāvoklis pēc noklusējuma nemainās.

Tieši laukā komentēt risinājumam varat pievienot komentārus jebkurā formā. Visbiežāk viņi paskaidro, ko nozīmē katrs Tjūringa mašīnas stāvoklis.

Programmu var izpildīt nepārtraukti (F9) vai pa soļiem (F8). Komanda, kas tagad tiks izpildīta, ir iezīmēta ar zaļu fonu. Izpildes ātrums regulējams, izmantojot izvēlni Ātrums.

Uzdevumus Tjūringa mašīnai var saglabāt failos. Tiek saglabāts uzdevuma nosacījums, alfabēts, programma, komentāri un lentes sākotnējais stāvoklis. Ielādējot uzdevumu no faila un saglabājot to failā, lentes stāvoklis automātiski tiek ierakstīts buferī.

Ja pamanāt kļūdu vai jums ir ieteikumi, komentāri, sūdzības, pieprasījumi un paziņojumi, rakstiet uz .

Tehniskās prasības

Programma darbojas saskaņā ar līnijas operētājsistēmām Windows jebkurā modernā datorā.

Licence

Programma ir bezmaksas nekomerciālai lietošanai. Programmas pirmkods netiek izplatīts.

Programma nāk ar kā ir”, tas ir, autors neuzņemas nekādu atbildību par visām iespējamām tā izmantošanas sekām, tostarp morāliem un materiāliem zaudējumiem, aprīkojuma kļūmēm, fiziskām un garīgām traumām.

Ievietojot programmu citās vietnēs, ir nepieciešama saite uz avotu.

1. 1) materiālu publicēšana jebkurā formā, tostarp materiālu ievietošana citās tīmekļa vietnēs;
2. 2) nepabeigtu vai izmainītu materiālu izplatīšana;
3. 3) materiālu iekļaušana kolekcijās jebkuros medijos;
4. 4) komerciālu labumu gūšana no materiālu pārdošanas vai citādas izmantošanas.

Materiālu lejupielāde nozīmē, ka esat piekritis šī licences līguma noteikumiem.

Lejupielādēt

Pēc arhīva izpakošanas programma ir darba stāvoklī un tai nav nepieciešama papildu instalēšana.

1. Tjūringa mašīnas apraksts. 3

1.1. Tjūringa mašīnas kā algoritma īpašības. 5

2. Algoritmu sarežģītība. 7

2.1 Problēmu sarežģītība.. 9

3. Tjūringa mašīna un algoritmiski neatrisināmas problēmas.. 12

Secinājums. 16

Atsauces.. 18

Ievads

Tjūringa mašīna ir ļoti vienkārša skaitļošanas ierīce. Tas sastāv no bezgalīga garuma lentes, kas sadalīta šūnās, un galviņas, kas pārvietojas pa lenti un spēj lasīt un rakstīt rakstzīmes. Arī Tjūringa mašīnai ir tāds raksturlielums kā stāvoklis, ko var izteikt kā veselu skaitli no nulles līdz noteiktai maksimālajai vērtībai. Atkarībā no stāvokļa Tjūringa mašīna var veikt vienu no trim darbībām: ierakstīt šūnā rakstzīmi, pārvietot vienu šūnu pa labi vai pa kreisi un iestatīt iekšējo stāvokli.

Tjūringa mašīna ir ārkārtīgi vienkārša, taču tā var palaist gandrīz jebkuru programmu. Lai veiktu visas šīs darbības, tiek nodrošināta īpaša noteikumu tabula, kurā norādīts, ko darīt ar dažādām pašreizējo stāvokļu un no lentes nolasīto rakstzīmju kombinācijām.

1947. gadā Alans Tjūrings paplašināja definīciju, lai aprakstītu "universālo Tjūringa mašīnu". Vēlāk atsevišķu problēmu klašu risināšanai tika ieviesta tās dažādība, kas ļāva veikt nevis vienu, bet vairākus uzdevumus.

1. Tjūringa mašīnas apraksts

Šī darba tapšanas aizvēsture ir saistīta ar Deivida Hilberta neatrisināto matemātisko problēmu formulēšanu Starptautiskajā matemātiķu kongresā Parīzē 1900. gadā. Viens no tiem bija parastās aritmētikas aksiomu sistēmas konsekvences pierādīšanas uzdevums, ko Hilberts vēlāk precizēja kā "izlemjamības problēmu" - atrašana. vispārīga metode, lai noteiktu dotā apgalvojuma iespējamību formālās loģikas valodā.

Tjūringa raksts tikko sniedza atbildi uz šo problēmu – Hilberta otrā problēma izrādījās neatrisināma. Taču Tjūringa darba nozīme pārsniedza problēmu, kuras dēļ tas tika uzrakstīts.

Šeit ir šī Džona Hopkrofta darba apraksts: "Strādājot pie Hilberta problēmas, Tjūringam bija jāsniedz skaidra definīcija pašam metodes jēdzienam. Sākot no intuitīvās idejas par metodi kā sava veida algoritmu, t.i. procedūra, kuru var veikt mehāniski, bez radošas iejaukšanās , viņš parādīja, kā šo ideju var iemiesot detalizēta skaitļošanas procesa modeļa veidā. Rezultātā iegūtais aprēķina modelis, kurā katrs algoritms tika sadalīts vienkāršu secībā , elementārie soļi, bija loģiska konstrukcija, ko vēlāk sauca par Tjūringa mašīnu.

Tjūringa mašīna ir ierobežotā automāta modeļa paplašinājums, paplašinājums, kas ietver potenciāli bezgalīgu atmiņu ar iespēju pārvietoties (pārvietoties) no pašlaik skatītās šūnas uz tās kreiso vai labo kaimiņu.

Formāli Tjūringa mašīnu var raksturot šādi. Ļaujiet dot:

ierobežota stāvokļu kopa - Q, kurā var atrasties Tjūringa mašīna;

ierobežots lentes simbolu kopums - Г;

funkcija δ (pārejas funkcija vai programma), ko iegūst, kartējot pāri no Dekarta reizinājuma Q x Г (mašīna atrodas stāvoklī qi un apseko simbolu gi) Dekarta reizinājuma Q x Г x (L) trīskāršā. , R) (iekārta pāriet stāvoklī qi, aizstāj rakstzīmi gi ar rakstzīmi gj un pārvieto pa kreisi vai pa labi vienu lentes rakstzīmi) – Q x G --> Q x G x (L,R)

viena rakstzīme no G-->e (tukšs);

apakškopa Σ є Г - -> ir definēta kā lentes ievades simbolu apakškopa, un e є (Г - Σ);

viens no stāvokļiem - q0 є Q ir iekārtas sākotnējais stāvoklis.

Atrisināmo uzdevumu uzdod, ierakstot lentē noteiktu skaitu simbolu no kopas Σ є Г - Si є Σ:

eS1S2S3S4... ... ...Sne

pēc kura mašīna tiek pārslēgta sākuma stāvoklī un galva tiek iestatīta uz galējo kreiso netukšo simbolu (q0,w) –, pēc kura saskaņā ar norādīto pārejas funkciju (qi,Si) - -> (qj, Sk, L vai R), iekārta sāk nomainīt skatāmās rakstzīmes, pārvietot galvu pa labi vai pa kreisi un pāriet uz citiem stāvokļiem, ko nosaka pārejas funkcijas.

Iekārta apstājas, ja pārejas funkcija nav definēta pārim (qi,Si).

Alans Tjūrings ierosināja, ka jebkuru algoritmu šī vārda intuitīvā nozīmē var attēlot ar līdzvērtīgu Tjūringa mašīnu. Šis pieņēmums ir pazīstams kā Baznīcas–Tjūringa tēze. Katrs dators var simulēt Tjūringa mašīnu (operācijas šūnu pārrakstīšanai, salīdzināšanai un pārvietošanai uz citu blakus esošo šūnu, ņemot vērā mašīnas stāvokļa izmaiņas). Līdz ar to viņš var modelēt algoritmus jebkurā formālismā, un no šī darba izriet, ka visi datori (neatkarīgi no jaudas, arhitektūras utt.) ir līdzvērtīgi algoritmisko uzdevumu risināšanas fundamentālās iespējas ziņā.

1.1. Tjūringa mašīnas kā algoritma īpašības

Tjūringa mašīnas piemērā algoritmu īpašības ir labi izsekotas. Lūdziet studentus parādīt, ka Tjūringa mašīnai ir visas algoritma īpašības.

diskrētums. Tjūringa mašīna var pāriet uz (k + 1)-to soli tikai pēc katra soļa izpildes, jo katrs solis nosaka, kāds būs (k + 1)-tais solis.

Skaidrība. Katrā solī šūnā tiek ierakstīts simbols no alfabēta, automāts veic vienu kustību (L, P, N), un Tjūringa mašīna nonāk kādā no aprakstītajiem stāvokļiem.

Noteiktība. Katrā Tjūringa mašīnas tabulas šūnā ir ierakstīta tikai viena opcija. Katrā solī rezultāts ir unikāli definēts, tāpēc problēmas risināšanas soļu secība ir unikāli definēta, t.i. ja Tjūringa mašīnai tiek ievadīts viens un tas pats ievades vārds, tad izvadvārds katru reizi būs vienāds.

Efektivitāte. Satura ziņā katra soļa rezultāti un visa darbību secība ir unikāli noteikti; ierobežotā soļu skaitā tiks iegūta atbilde uz problēmas jautājumu.

Masu raksturs. Katra Tjūringa mašīna ir definēta pār visiem derīgajiem vārdiem no alfabēta, un tā ir masas īpašība. Katra Tjūringa mašīna ir paredzēta vienas klases uzdevumu risināšanai, t.i. Katram uzdevumam ir sava (jaunā) Tjūringa mašīna.

2. Algoritmu sarežģītība

Algoritma sarežģītību nosaka tā izpildei nepieciešamā skaitļošanas jauda. Algoritma skaitļošanas sarežģītību bieži mēra divos terminos: T (laika sarežģītība) un S (telpas sarežģītība jeb atmiņas prasības). Gan T, gan S parasti tiek attēlotas kā n funkcijas, kur n ir ievades lielums. (Ir arī citi sarežģītības mērīšanas veidi: nejaušo bitu skaits, sakaru kanāla platums, datu apjoms utt.)

Parasti algoritma skaitļošanas sarežģītību izsaka, izmantojot apzīmējumu "Lielais O", t.i., to apraksta ar skaitļošanas sarežģītības pakāpi. Šis ir vienkārši sarežģītības paplašināšanas termins, kas visstraujāk pieaug ar n, visi zemākas kārtas termini tiek ignorēti. Piemēram, ja noteiktā algoritma laika sarežģītība ir 4n2+7n+12, tad skaitļošanas sarežģītība ir n2, kas rakstīta kā O(n2).

Šādā veidā izmērītā laika sarežģītība ir neatkarīga no ieviešanas. Jums nav jāzina precīzs dažādu instrukciju izpildes laiks, dažādu mainīgo attēlošanai izmantoto bitu skaits vai pat procesora ātrums. Viens dators varētu būt par 50 procentiem ātrāks nekā cits, un trešajam datu kopne varētu būt divreiz platāka, taču algoritma sarežģītība, ko mēra pēc lieluma, nemainītos. Tā nav krāpšanās, strādājot ar tik sarežģītiem algoritmiem kā tie, kas aprakstīti šajā grāmatā, visu pārējo var atstāt novārtā (līdz nemainīgam faktoram), salīdzinot ar sarežģītības pakāpi.

Šis apzīmējums ļauj redzēt, kā ievades lielums ietekmē laika un atmiņas prasības. Piemēram, ja T = O(n), tad, dubultojot ievadi, tiks dubultots arī algoritma izpildes laiks. Ja T=O(2n), tad viena bita pievienošana ieejas datiem dubultos algoritma izpildes laiku.

Parasti algoritmus klasificē pēc to laika vai telpas sarežģītības. Algoritmu sauc par konstantu, ja tā sarežģītība nav atkarīga no n: 0(1). Algoritms ir lineārs, ja tā laika sarežģītība ir O(n). Algoritmi var būt kvadrātveida, kubiski utt. Visi šie algoritmi ir polinomi, to sarežģītība ir O(m), kur m ir konstante. Algoritmus ar polinoma laika sarežģītību sauc par polinoma laika algoritmiem

Algoritmus, kuru sarežģītība ir vienāda ar O(tf(n)), kur t ir konstante, kas lielāka par 1, un f(n) ir kāda n polinoma funkcija, sauc par eksponenciāliem. Eksponenciālo algoritmu apakškopu, kuras sarežģītība ir O(cf(n)), kur c ir konstante un f(n) aug ātrāk nekā konstante, bet lēnāk nekā lineāra funkcija, sauc par superpolinomu.

Ideālā gadījumā kriptogrāfs vēlētos apgalvot, ka vislabākajam algoritmam izstrādāta šifrēšanas algoritma pārtraukšanai ir eksponenciāla laika sarežģītība. Praksē visspēcīgākie apgalvojumi, ko var sniegt, ņemot vērā pašreizējo skaitļošanas sarežģītības teorijas stāvokli, ir šādi: "visiem zināmajiem algoritmiem noteiktas kriptosistēmas izjaukšanai ir superpolinoma laika sarežģītība". Tas ir, mums zināmajiem uzbrukuma algoritmiem ir superpolinomiāla laika sarežģītība, taču pagaidām nav iespējams pierādīt, ka uzbrukuma algoritmu ar polinoma laika sarežģītību nevar atklāt. Aprēķinu sarežģītības teorijas attīstība kādreiz ļaus izveidot algoritmus, kuriem ar matemātisku precizitāti var izslēgt algoritmu ar polinoma atvēršanas laiku esamību.