Π”ΠΈΠΏΠ»ΠΎΠΌΡ‹, курсовыС, Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚Ρ‹, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Ρ‹Π΅...
Брочная ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π² ΡƒΡ‡Ρ‘Π±Π΅

ОписаниС машин Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°

Π Π΅Ρ„Π΅Ρ€Π°Ρ‚ΠŸΠΎΠΌΠΎΡ‰ΡŒ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈΠ£Π·Π½Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒΠΌΠΎΠ΅ΠΉ Ρ€Π°Π±ΠΎΡ‚Ρ‹

НаконСц, машина М3 ΡƒΠ±ΠΈΡ€Π°Π΅Ρ‚ ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΈ' ΠΈ ΠΎΡΡ‚анавливаСтся Π½Π°Π΄ ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ нСпустым символом. (Если вся Π»Π΅Π½Ρ‚Π° пуста, Ρ‚ΠΎ ΠΌΠ°ΡˆΠΈΠ½Π° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΡΡ‚Π°Π½ΠΎΠ²ΠΈΡ‚ΡŒΡΡ Π² Π»ΡŽΠ±ΠΎΠΌ мСстС.) Машина А/Π· двиТСтся Π½Π°ΠΏΡ€Π°Π²ΠΎ, мСняя символы (Π›, 1) Π½Π° (Π›, 0), ΠΏΠΎΠΊΠ° Π½Π΅ Π΄ΠΎΡΡ‚ΠΈΠ³Π½Π΅Ρ‚ ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ нСпустого символа Π² ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π΅. Π­Ρ‚ΠΎΡ‚ символ ΠΎΠ½Π° Π½Π΅ ΠΌΠ΅Π½ΡΠ΅Ρ‚ ΠΈ ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅Ρ‚ Π΄Π²ΠΈΠΆΠ΅Π½ΠΈΠ΅ Π½Π°ΠΏΡ€Π°Π²ΠΎ, замСняя ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΈ Π½Π° 0, ΠΏΠΎΠΊΠ° Π½Π΅ Π΄ΠΎΡΡ‚ΠΈΠ³Π½Π΅Ρ‚ символа с ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΎΠΉ 0… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ОписаниС машин Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π° (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

ΠŸΡ€ΠΈ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² Π½Π° ΠΌΠ°ΡˆΠΈΠ½Π°Ρ… Π’Ρ‹ΠΎΡ€ΠΈΠ½Π³Π° постоянно приходится ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΎΠ΄Π½ΠΈ ΠΈ Ρ‚Π΅ ΠΆΠ΅ стандартныС дСйствия. Π’ ΡΡ‚ΠΎΠΌ ΠΏΠΎΠ΄Ρ€Π°Π·Π΄Π΅Π»Π΅ ΠΌΡ‹ ΠΎΠΏΠΈΡˆΠ΅ΠΌ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ стандартныС ΠΏΡ€ΠΈΡ‘ΠΌΡ‹ построСния машин Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°. Π’ Π΄Π°Π»ΡŒΠ½Π΅ΠΉΡˆΠ΅ΠΌ ΠΌΡ‹ Π±ΡƒΠ΄Π΅ΠΌ ΠΏΠΎΠ΄Ρ€Π°Π·ΡƒΠΌΠ΅Π²Π°Ρ‚ΡŒ эти ΠΏΡ€ΠΈΡ‘ΠΌΡ‹ ΠΈ Π½Π΅ Π²Ρ‹ΠΏΠΈΡΡ‹Π²Π°Ρ‚ΡŒ явно Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ ΠΈΡ… ΠΏΡ€ΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ.

ΠŸΡ€Π΅ΠΆΠ΄Π΅ всСго ΠΎΠ±Ρ€Π°Ρ‚ΠΈΠΌ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ ΠΎΠ±Ρ‹Ρ‡Π½ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ разбиваСтся Π½Π° Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΎ шагов. Если ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΈΠ· Ρ‚Π°ΠΊΠΈΡ… шагов рСализуСтся Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ машиной Π’Ρ‹ΠΎΡ€ΠΈΠ½Π³Π°, Ρ‚ΠΎ Π²Π΅ΡΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ рСализуСтся ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ соСдинСниСм Π»Ρ‚ΡˆΠΈΠ½ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°. ΠŸΡ€ΠΈΠ²Π΅Π΄Ρ‘ΠΌ Π½Π΅Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠ΅ описаниС этой конструкции.

ΠŸΠ΅Ρ€Π΅ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΠΌ состояния соСдиняСмых машин Ρ‚Π°ΠΊ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ ΠΎΠ½ΠΈ стали ΠΏΠΎΠΏΠ°Ρ€Π½ΠΎ Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹. ПослС этого мноТСством состояний ΠΌΠ°ΡˆΠΈΠ½Ρ‹, которая являСтся ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ соСдинСниСм, Π½Π°Π·ΠΎΠ²Ρ‘ΠΌ объСдинСниС мноТСств состояний соСдиняСмых машин. Π’Π°Π±Π»ΠΈΡ†Π° ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠ² соСдинСния составлСна ΠΈΠ· Ρ‚Π°Π±Π»ΠΈΡ† ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠ² соСдиняСмых машин Π·Π° ΠΈΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ΠΌ Ρ‚ΠΎΠ³ΠΎ, Ρ‡Ρ‚ΠΎ ΠΈΠ· Ρ„ΠΈΠ½Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния (Π³ — 1)-ΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ осущСствляСтся ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ Π² Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС Π³-ΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹. Π€ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹Π΅ состояния послСднСй ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΡΠ²Π»ΡΡŽΡ‚ΡΡ Ρ„ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ состояниями всСго соСдинСния машин.

Один ΠΈΠ»ΠΈ нСсколько шагов Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΎΠ³ΡƒΡ‚ ΠΏΠΎΠ²Ρ‚ΠΎΡ€ΡΡ‚ΡŒΡΡ цикличСски Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° выполняСтся Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ условиС. Π’Π°ΠΊΠΈΠ΅ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡ‹ ΠΌΡ‹ ΠΏΡ€Π΅Π΄ΡΡ‚авляСм Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½ΠΎ описанному Π²Ρ‹ΡˆΠ΅ соСдинСнию машин. Но Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ ΠΈΠ· Ρ‡Π°ΡΡ‚ΠΈ Ρ„ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… состояний (Π³ — 1)-ΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ осущСствляСтся ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ Π² Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС (Π³ — 1)-ΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ (условиС повторСния Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ), Π° ΠΈΠ· ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Ρ… — Π² Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС Π³-ΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹. Аналогично ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΠΈΡΠ°Ρ‚ΡŒ Π±ΠΎΠ»Π΅Π΅ слоТныС Ρ†ΠΈΠΊΠ»Ρ‹, Π² ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… повторяСтся Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ Π±Π»ΠΎΠΊΠ° соСдиняСмых машин.

Π”Ρ€ΡƒΠ³ΠΎΠΉ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ³ΠΎ соСдинСния состоит Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ вмСсто Π²Ρ‚ΠΎΡ€ΠΎΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ Π½Π°Π±ΠΎΡ€ машин, каТдая ΠΈΠ· ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΡ‚Π²Π΅Ρ‡Π°Π΅Ρ‚ ΠΎΠ΄Π½ΠΎΠΌΡƒ ΠΈΠ· Ρ„ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹Ρ… состояний ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹. Π’ ΡΡ‚ΠΎΠΌ случаС ΠΈΠ· Ρ„ΠΈΠ½Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ дСлаСтся ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ Π² Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС Ρ‚ΠΎΠΉ ΠΌΠ°ΡˆΠΈΠ½Ρ‹, которая ΠΎΡ‚Π²Π΅Ρ‡Π°Π΅Ρ‚ этому Ρ„ΠΈΠ½Π°Π»ΡŒΠ½ΠΎΠΌΡƒ ΡΠΎΡΡ‚ΠΎΡΠ½ΠΈΡŽ. Π’Π°ΠΊΠΎΠ΅ соСдинСниС Π±ΡƒΠ΄Π΅ΠΌ Π½Π°Π·Ρ‹Π²Π°Ρ‚ΡŒ Π²Π΅Π΅Ρ€Π½Ρ‹ΠΌ.

Π’Π΅ΠΏΠ΅Ρ€ΡŒ ΠΎΠ±Ρ€Π°Ρ‚ΠΈΠΌ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° Π΄Π²ΠΎΠΉΡΡ‚Π²Π΅Π½Π½ΡƒΡŽ Ρ€ΠΎΠ»ΡŒ мноТСства состояний ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°. Π’ΠΎ-ΠΏΠ΅Ρ€Π²Ρ‹Ρ…, состояниС фиксируСт ΠΈΠ½ΡΡ‚Ρ€ΡƒΠΊΡ†ΠΈΡŽ ΠΏΠΎ Π΄Π°Π»ΡŒΠ½Π΅ΠΉΡˆΠΈΠΌ дСйствиям. Но ΡΠΎΡΡ‚ояния ΠΌΠΎΠΆΠ½ΠΎ Ρ‚Π°ΠΊΠΆΠ΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ для хранСния ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΈ, привязанной ΠΊ ΡƒΠΏΡ€Π°Π²Π»ΡΡŽΡ‰Π΅ΠΉ Π³ΠΎΠ»ΠΎΠ²ΠΊΠ΅ ΠœΠ’. Π’Π°ΠΊΡƒΡŽ ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ ΠΌΠΎΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π² Π»ΡŽΠ±ΠΎΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ‚ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ для Π²Ρ‹Π±ΠΎΡ€Π° ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… дСйствий. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ мноТСство состояний ΠœΠ’ ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎ, такая «ΠΎΠΏΠ΅Ρ€Π°Ρ‚ивная ΠΏΠ°ΠΌΡΡ‚ΡŒ» ΠΈΠΌΠ΅Π΅Ρ‚ лишь ΠΊΠΎΠ½Π΅Ρ‡Π½ΡƒΡŽ Ρ‘ΠΌΠΊΠΎΡΡ‚ΡŒ. Π‘ Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ‚ΠΎΡ‡ΠΊΠΈ зрСния использованиС «ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ памяти» МВ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ мноТСство состояний ΠœΠ’ Q прСдставлСно Π² Π²ΠΈΠ΄Π΅ Π΄Π΅ΠΊΠ°Ρ€Ρ‚ΠΎΠ²Π° произвСдСния Π‘ Ρ… М Π΄Π²ΡƒΡ… ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… мноТСств. Π’ ΡΠΎΡΡ‚оянии q = (с, 777.) вторая ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π° Ρ‚ ΠΎΡ‚Π²Π΅Ρ‡Π°Π΅Ρ‚ Π·Π° ΡΠΎΠ΄Π΅Ρ€ΠΆΠΈΠΌΠΎΠ΅ «ΠΎΠΏΠ΅Ρ€Π°Ρ‚ΠΈΠ²Π½ΠΎΠΉ памяти».

Аналогично мноТСству состояний Π°Π»Ρ„Π°Π²ΠΈΡ‚ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π° Ρ‚Π°ΠΊΠΆΠ΅ ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°ΡΡˆΠΈΡ€ΡΡ‚ΡŒ. Π’Π°ΠΊΠΈΠΌ способом ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠΏΠΈΡΡ‹Π²Π°Ρ‚ΡŒ расстановку «ΠΏΠΎΠΌΠ΅Ρ‚ΠΎΠΊ» Π½Π° Ρ€Π°Π±ΠΎΡ‡Π΅ΠΉ Π»Π΅Π½Ρ‚Π΅. «ΠŸΠΎΠΌΠ΅Ρ‚ΠΊΠΈ» хранят ΠΈΠ½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΡŽ Π² ΡΡ‡Π΅ΠΉΠΊΠ°Ρ… Π»Π΅Π½Ρ‚Ρ‹.

ΠŸΡ€ΠΈΠ²Π΅Π΄Ρ‘ΠΌ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ использования этих ΠΏΡ€ΠΈΡ‘ΠΌΠΎΠ² Π² Ρ€Π°ΡΡΡƒΠΆΠ΄Π΅Π½ΠΈΡΡ… ΠΎ ΠΌΠ°ΡˆΠΈΠ½Π°Ρ… Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€ 4.14 {"чистоС" соСдинСниС машин Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°). Π’ Π΄Π°Π»ΡŒΠ½Π΅ΠΉΡˆΠ΅ΠΌ ΠΌΡ‹ Π±ΡƒΠ΄Π΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ соСдинСниС машин Π’Ρ‹ΠΎΡ€ΠΈΠ½Π³Π° для построСния ΠΌΠ°ΡˆΠΈΠ½Ρ‹, Π²Ρ‹Ρ‡ΠΈΡΠ»ΡΡŽΡ‰Π΅ΠΉ ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ вычисляСмых ΠœΠ’ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ[1]). ΠžΠ±Ρ€Π°Ρ‚ΠΈΠΌ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π½Π° ΠΎΠ΄Π½Ρƒ Π²ΠΎΠ·Π½ΠΈΠΊΠ°ΡŽΡ‰ΡƒΡŽ здСсь Ρ‚Ρ€ΡƒΠ΄Π½ΠΎΡΡ‚ΡŒ. Π’ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠΈ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π° Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠœΠ’ Π½ΠΈΡ‡Π΅Π³ΠΎ Π½Π΅ Π³ΠΎΠ²ΠΎΡ€ΠΈΡ‚ся ΠΎ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠΈ Π³ΠΎΠ»ΠΎΠ²ΠΊΠΈ. Π‘ Π΄Ρ€ΡƒΠ³ΠΎΠΉ стороны, Π² Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠΉ ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΈ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ ΠΌΡ‹ ΠΏΡ€Π΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅ΠΌ, Ρ‡Ρ‚ΠΎ Π³ΠΎΠ»ΠΎΠ²ΠΊΠ° находится Π½Π°Π΄ ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ нСпустым символом. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ описанная Π²Ρ‹ΡˆΠ΅ конструкция соСдинСния машин Π½Π°ΠΏΡ€ΡΠΌΡƒΡŽ Π½Π΅ΠΏΡ€ΠΈΠ³ΠΎΠ΄Π½Π° для вычислСния ΠΊΠΎΠΌΠΏΠΎΠ·ΠΈΡ†ΠΈΠΈ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΉ.

Π­Ρ‚Π° Ρ‚Ρ€ΡƒΠ΄Π½ΠΎΡΡ‚ΡŒ прСодолСваСтся построСниСм ΠΏΠΎ ΠœΠ’ М Ρ‚Π°ΠΊΠΎΠΉ ΠœΠ’ М которая Π½Π° Π»ΡŽΠ±ΠΎΠΌ Π²Ρ…ΠΎΠ΄Π΅ Π΄Π°Ρ‘Ρ‚ Ρ‚ΠΎΡ‚ ΠΆΠ΅ самый Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚, Ρ‡Ρ‚ΠΎ ΠΈ А/, Π½ΠΎ Π² ΠΊΠΎΠ½Ρ†Π΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΏΠΎΠΌΠ΅Ρ‰Π°Π΅Ρ‚ Π³ΠΎΠ»ΠΎΠ²ΠΊΡƒ Π½Π°Π΄ ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ нСпустым символом.

Машина М' ΠΈΠΌΠ΅Π΅Ρ‚ Π°Π»Ρ„Π°Π²ΠΈΡ‚ А Ρ… {0,1}, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ состоит ΠΈΠ· ΠΏΠ°Ρ€ (символ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° А ΠΌΠ°ΡˆΠΈΠ½Ρ‹ А/, ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠ°). ΠΠ΅Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎ ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠ° 1 ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚, Ρ‡Ρ‚ΠΎ Π±Ρ‹Π» Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ Ρ‚Π°ΠΊΡ‚ Ρ€Π°Π±ΠΎΡ‚Ρ‹, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ ΠΏΡ€ΠΎΡ‡ΠΈΡ‚Π°Π½Π°, ячСйка, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ находится символ. ΠŸΠ°Ρ€Ρ‹ Π²ΠΈΠ΄Π°, (Π°, 0) ΠΎΡ‚ΠΎΠΆΠ΄Π΅ΡΡ‚Π²Π»ΡΡŽΡ‚ΡΡ с ΠΈΡΡ…ΠΎΠ΄Π½Ρ‹ΠΌ Π°Π»Ρ„Π°Π²ΠΈΡ‚ΠΎΠΌ ΠΌΠ°ΡˆΠΈΠ½Ρ‹. Π’ Ρ‡Π°ΡΡ‚ности, пустым символом ΠΌΠ°ΡˆΠΈΠ½Ρ‹ являСтся символ (Π›, 0), Π° Π·Π°ΠΏΠΈΡΡŒ Π²Ρ…ΠΎΠ΄Π° ΠΌΠ°ΡˆΠΈΠ½Ρ‹ М Ρ†Π΅Π»ΠΈΠΊΠΎΠΌ состоит ΠΈΠ· ΡΠΈΠΌΠ²ΠΎΠ»ΠΎΠ² ΠΌΠ°ΡˆΠΈΠ½Ρ‹ А/' с Π½ΡƒΠ»Π΅Π²ΠΎΠΉ ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΎΠΉ, Ρ‚Π°ΠΊ Ρ‡Ρ‚ΠΎ описанноС Π²Ρ‹ΡˆΠ΅ свойство ΠΏΠΎΠΌΠ΅Ρ‚ΠΎΠΊ ΠΏΠ΅Ρ€Π΅Π΄ Π½Π°Ρ‡Π°Π»ΠΎΠΌ Ρ€Π°Π±ΠΎΡ‚Ρ‹ выполняСтся.

ОпишСм ΠΌΠ°ΡˆΠΈΠ½Ρƒ М' ΠΊΠ°ΠΊ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ соСдинСниС машин А/], М2 ΠΈ Πœ3. Машина М ΠΌΠΎΠ΄Π΅Π»ΠΈΡ€ΡƒΠ΅Ρ‚ Ρ€Π°Π±ΠΎΡ‚Ρƒ А/, мСняя ΠΏΠ΅Ρ€Π²Ρ‹Π΅ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Ρ‹ символов Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° Ρ‚ΠΎΡ‡Π½ΠΎ Ρ‚Π°ΠΊ ΠΆΠ΅, ΠΊΠ°ΠΊ это Π΄Π΅Π»Π°Π΅Ρ‚ машина А/. Π’ΠΎ Π²Ρ‚ΠΎΡ€Ρ‹Ρ… ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π°Ρ… машина Mj ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚ ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠ΅ Π²Ρ‹ΡˆΠ΅ свойство. Π”Ρ€ΡƒΠ³ΠΈΠΌΠΈ словами, Π΅Ρ‘ Ρ‚Π°Π±Π»ΠΈΡ†Π° ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠ² ΠΈΠΌΠ΅Π΅Ρ‚ Π²ΠΈΠ΄.

ОписаниС машин Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°.

Π€ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹Π΅ состояния Ρƒ Mi Ρ‚Π΅ ΠΆΠ΅, Ρ‡Ρ‚ΠΎ ΠΈ Ρƒ М.

Машина М2 ΠΈΡ‰Π΅Ρ‚ самый Π»Π΅Π²Ρ‹ΠΉ символ, Ρƒ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠ° Ρ€Π°Π²Π½Π° 1. ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ М2 Π½Π°Ρ‡ΠΈΠ½Π°Π΅Ρ‚ Ρ€Π°Π±ΠΎΡ‚Ρƒ послС Π·Π°Π²Π΅Ρ€ΡˆΠ΅Π½ΠΈΡ Ρ€Π°Π±ΠΎΡ‚Ρ‹ Mi, ΠΌΠΎΠΆΠ½ΠΎ Π±Π΅Π· ограничСния общности ΡΡ‡ΠΈΡ‚Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎ этот символ располоТСн Π½Π΅ ΠΏΡ€Π°Π²Π΅Π΅ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ полоТСния Π³ΠΎΠ»ΠΎΠ²ΠΊΠΈ. Π’ ΡΠΈΠ»Ρƒ сформулированного Π²Ρ‹ΡˆΠ΅ свойства ΠΏΠΎΠΌΠ΅Ρ‚ΠΎΠΊ ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ слСва символом с ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΎΠΉ 0 Π±ΡƒΠ΄Π΅Ρ‚ пустой символ. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Ρ‚Π°Π±Π»ΠΈΡ†Ρƒ ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠ² ΠΌΠ°ΡˆΠΈΠ½Ρ‹ М2 ΠΌΠΎΠΆΠ½ΠΎ Π·Π°Π΄Π°Ρ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ:

ОписаниС машин Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°.

НаконСц, машина М3 ΡƒΠ±ΠΈΡ€Π°Π΅Ρ‚ ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΈ[2]' ΠΈ ΠΎΡΡ‚анавливаСтся Π½Π°Π΄ ΠΏΠ΅Ρ€Π²Ρ‹ΠΌ нСпустым символом. (Если вся Π»Π΅Π½Ρ‚Π° пуста, Ρ‚ΠΎ ΠΌΠ°ΡˆΠΈΠ½Π° ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΡΡ‚Π°Π½ΠΎΠ²ΠΈΡ‚ΡŒΡΡ Π² Π»ΡŽΠ±ΠΎΠΌ мСстС.) Машина А/Π· двиТСтся Π½Π°ΠΏΡ€Π°Π²ΠΎ, мСняя символы (Π›, 1) Π½Π° (Π›, 0), ΠΏΠΎΠΊΠ° Π½Π΅ Π΄ΠΎΡΡ‚ΠΈΠ³Π½Π΅Ρ‚ ΠΏΠ΅Ρ€Π²ΠΎΠ³ΠΎ нСпустого символа Π² ΠΏΠ΅Ρ€Π²ΠΎΠΉ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ‚Π΅. Π­Ρ‚ΠΎΡ‚ символ ΠΎΠ½Π° Π½Π΅ ΠΌΠ΅Π½ΡΠ΅Ρ‚ ΠΈ ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅Ρ‚ Π΄Π²ΠΈΠΆΠ΅Π½ΠΈΠ΅ Π½Π°ΠΏΡ€Π°Π²ΠΎ, замСняя ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΈ Π½Π° 0, ΠΏΠΎΠΊΠ° Π½Π΅ Π΄ΠΎΡΡ‚ΠΈΠ³Π½Π΅Ρ‚ символа с ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΎΠΉ 0. Π’ ΡΡ‚ΠΎΡ‚ ΠΌΠΎΠΌΠ΅Π½Ρ‚ ΠΎΠ½Π° Π½Π°Ρ‡ΠΈΠ½Π°Π΅Ρ‚ Π΄Π²ΠΈΠ³Π°Ρ‚ΡŒΡΡ Π½Π°Π»Π΅Π²ΠΎ Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠΈΡ‚ (ΡƒΠΆΠ΅ СдинствСнный) символ с ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΎΠΉ 1. Π—Π°ΠΌΠ΅Π½ΠΈΠ² ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΡƒ этого символа Π½Π° 0, машина Π›/Π· останавливаСтся. Π’Π°Π±Π»ΠΈΡ†Π° ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠ² ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Мз Π·Π°Π΄Π°Ρ‘тся ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ (Π° ΠΏΡ€ΠΎΠ±Π΅Π³Π°Π΅Ρ‚ мноТСство нСпустых символов Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°):

ОписаниС машин Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°.

ΠŸΡ€ΠΎΠ²Π΅Ρ€ΠΊΠ° коррСктности этой Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ прСдоставляСтся Ρ‡ΠΈΡ‚Π°Ρ‚Π΅Π»ΡŽ Π² ΠΊΠ°Ρ‡Π΅ΡΡ‚Π²Π΅ ΠΏΠΎΠ»Π΅Π·Π½ΠΎΠ³ΠΎ упраТнСния.

Π—Π°ΠΌΠ΅Ρ‡Π°Π½ΠΈΠ΅ 4.15. Иногда Π±Ρ‹Π²Π°Π΅Ρ‚ ΠΆΠ΅Π»Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ Π½Π΅ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Ρ„ΠΈΠΊΡΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π³ΠΎΠ»ΠΎΠ²ΠΊΠΈ Π² ΠΊΠΎΠ½Ρ†Π΅ Ρ€Π°Π±ΠΎΡ‚Ρ‹, Π½ΠΎ ΠΈ ΠΏΠΎΡ‚Ρ€Π΅Π±ΠΎΠ²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Ρ„ΠΈΠ½Π°Π»ΡŒΠ½ΠΎΠ΅ состояниС ΠΌΠ°ΡˆΠΈΠ½Ρ‹ М' совпадало с Ρ„ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹ΠΌ состояниСм ΠΌΠ°ΡˆΠΈΠ½Ρ‹ М. Для этого Π½ΡƒΠΆΠ½ΠΎ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ Π²Π΅Π΅Ρ€Π½ΠΎΠ΅ соСдинСниС, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ Ρ„ΠΈΠ½Π°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния запускаСтся своя копия ΠΌΠ°ΡˆΠΈΠ½Ρ‹ М-2 ΠΈΠ· ΠΎΠΏΠΈΡΠ°Π½Π½ΠΎΠΉ Π²Ρ‹ΡˆΠ΅ конструкции.

Π—Π°Π΄Π°Ρ‡Π° 4.2. ΠŸΠΎΡΡ‚Ρ€ΠΎΠΉΡ‚Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρƒ Π’Ρ‹ΠΎΡ€ΠΈΠ½Π³Π°, Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ Ρ€Π°Π±ΠΎΡ‚Ρ‹ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ ΠΏΠΎ Π²Ρ…ΠΎΠ΄Π΅ it, v € {0,1}*, Ρ€Π°Π²Π΅Π½ 1, Ссли ΠΈ

ΠΈ v Π·Π°Π΄Π°ΡŽΡ‚ ΠΎΠ΄Π½ΠΎ ΠΈ Ρ‚ΠΎ ΠΆΠ΅ Π½Π°Ρ‚ΡƒΡ€Π°Π»ΡŒΠ½ΠΎΠ΅ число, ΠΈ Ρ€Π°Π²Π΅Π½ 0 Π² ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΎΠΌ случаС.

  • [1] Под вычисляСмой ΠœΠ’ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ ΠΌΡ‹ ΠΏΠΎΠ½ΠΈΠΌΠ°Π΅ΠΌ сСйчас частичноотобраТСниС Π²Ρ…ΠΎΠ΄ΠΎΠ² Π½Π° Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ‹ Ρ€Π°Π±ΠΎΡ‚Ρ‹.
  • [2] Напомним, Ρ‡Ρ‚ΠΎ с ΡΠΈΠΌΠ²ΠΎΠ»Π°ΠΌΠΈ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°, А ΠΌΠ°ΡˆΠΈΠ½Ρ‹ М ΠΌΡ‹ ΠΎΡ‚оТдСствили ΠΏΠ°Ρ€Ρ‹ с Π½ΡƒΠ»Π΅Π²ΠΎΠΉ ΠΏΠΎΠΌΠ΅Ρ‚ΠΊΠΎΠΉ, поэтому Π΄Π°Π½Π½Ρ‹ΠΉ шаг Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌ.
ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ