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

ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΠ° остановки ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°

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

Π’ ΠΌΠ°Ρ‚СматичСской Π»ΠΎΠ³ΠΈΠΊΠ΅ ΠΈ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΏΠΎΠ΄ Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΡΡ‚ΡŒΡŽ ΠΏΠΎΠ΄Ρ€Π°Π·ΡƒΠΌΠ΅Π²Π°ΡŽΡ‚ свойство Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΎΠ±Π»Π°Π΄Π°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ, ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‰ΠΈΠΌ ΠΏΠΎ Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅, Π²Ρ‹Π²ΠΎΠ΄ΠΈΠΌΠ° ΠΎΠ½Π° ΠΈΠ· ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²Π° аксиом Π΄Π°Π½Π½ΠΎΠΉ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΈΠ»ΠΈ Π½Π΅Ρ‚. ВСория называСтся Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠΉ, Ссли Ρ‚Π°ΠΊΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ сущСствуСт, ΠΈ Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠΉ, Π² ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΎΠΌ случаС. Π˜ΠΌΠ΅Π΅Ρ‚ мСсто Π±Ρ‹Ρ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ°: Π½Π΅ ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΠ΅Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° (ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°… Π§ΠΈΡ‚Π°Ρ‚ΡŒ Π΅Ρ‰Ρ‘ >

ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΠ° остановки ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π° (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсовая, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°Ρ)

ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΠ° остановки ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π° — это ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° построСния Ρ‚Π°ΠΊΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠ³ Π±Ρ‹ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ закончится ΠΈΠ»ΠΈ Π½Π΅Ρ‚ вычислСниС ΠΏΠΎ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ Π·Π°Π΄Π°Ρ‡Π΅. ΠžΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚ΡΡ, Ρ‡Ρ‚ΠΎ Π² ΠΎΠ±Ρ‰Π΅ΠΌ случаС Ρ‚Π°ΠΊΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ нСльзя ΠΏΠΎΡΡ‚Ρ€ΠΎΠΈΡ‚ΡŒ Π² ΠΏΡ€ΠΈΠ½Ρ†ΠΈΠΏΠ΅, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΉΡ‚ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‰ΠΈΠΉ ΠΏΠΎ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΉ машинС Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π° Π’ ΠΈ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΉ Π΅Π΅ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠΉ ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΈ qiaj ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ ΠΏΡ€ΠΈΠ΄Π΅Ρ‚ Π»ΠΈ машина Π’ Π² Π·Π°ΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ состояниС q0, Ссли Π½Π°Ρ‡Π½Π΅Ρ‚ Ρ€Π°Π±ΠΎΡ‚Ρƒ Π² ΡΡ‚ΠΎΠΉ ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΈ.

Если машина Π’, запущСнная Π² Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠΉ ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΈ qiaj, останавливаСтся (Ρ‚.Π΅. ΠΏΠΎΠΏΠ°Π΄Π°Π΅Ρ‚ Π² Π·Π°ΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½ΠΎΠ΅ состояниС) Ρ‡Π΅Ρ€Π΅Π· ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ число шагов, Ρ‚ΠΎ ΠΎΠ½Π° называСтся самопримСнимой, Π² ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΎΠΌ случаС — нСсамопримСнимой.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°.

НС ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΠ΅Ρ‚ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π° М, Ρ€Π΅ΡˆΠ°ΡŽΡ‰Π΅ΠΉ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡƒ самопримСнимости, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° самопримСнимости алгоритмичСски Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠ°.

Π”ΠΎΠΊΠ°Π·Π°Ρ‚Π΅Π»ΡŒΡΡ‚Π²ΠΎ.

ΠŸΡ€Π΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΎΠ΅, Ρ‚ΠΎ Π΅ΡΡ‚ΡŒ. ΠΏΡƒΡΡ‚ΡŒ сущСствуСт машина Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π° Π’, Ρ€Π΅ΡˆΠ°ΡŽΡ‰Π°Ρ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡƒ самопримСнимости Π² ΡƒΠΊΠ°Π·Π°Π½Π½ΠΎΠΌ Π²Ρ‹ΡˆΠ΅ смыслС. ΠŸΠΎΡΡ‚Ρ€ΠΎΠΈΠΌ Π½ΠΎΠ²ΡƒΡŽ ΠΌΠ°ΡˆΠΈΠ½Ρƒ Π’0, Π΄ΠΎΠ±Π°Π²ΠΈΠ² Π½ΠΎΠ²ΠΎΠ΅ состояниС q0* ΠΈ ΠΎΠ±ΡŠΡΠ²ΠΈΠ² Π΅Π³ΠΎ Π·Π°ΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ, Π° Ρ‚Π°ΠΊΠΆΠ΅ Π΄ΠΎΠ±Π°Π²ΠΈΠ² Π½ΠΎΠ²Ρ‹Π΅ ΠΊΠΎΠΌΠ°Π½Π΄Ρ‹ для состояния q0, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π±Ρ‹Π»ΠΎ Π·Π°ΠΊΠ»ΡŽΡ‡ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌ Π² Π’:

q0 a1> a1 Π‘ q0 (1).

q0 a2> a2 Π‘ q0 (2).

…q0 an> an Π‘ q0* (n).

Рассмотрим Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ Ρ€Π°Π±ΠΎΡ‚Ρƒ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ T0.

ΠŸΡƒΡΡ‚ΡŒ M — ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Π°Ρ машина. Если M — самопримСнима, Ρ‚ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½Π°Ρ конфигурация q1ai ΠΏΠ΅Ρ€Π΅ΠΉΠ΄Π΅Ρ‚ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠΎΠΌΠ°Π½Π΄ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ T Ρ‡Π΅Ρ€Π΅Π· ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ число шагов Π² ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΡŽ q0a1, Π΄Π°Π»Π΅Π΅ примСняСтся ΠΊΠΎΠΌΠ°Π½Π΄Π° (1), ΠΈ ΠΌΠ°ΡˆΠΈΠ½Π° T0 Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ ΠΎΡΡ‚ановится. Если M — нСсамопримСнима, Ρ‚ΠΎ Π½Π°Ρ‡Π°Π»ΡŒΠ½Π°Ρ конфигурация q1ai ΠΏΠ΅Ρ€Π΅ΠΉΠ΄Π΅Ρ‚ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΊΠΎΠΌΠ°Π½Π΄ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ T Ρ‡Π΅Ρ€Π΅Π· ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ число шагов Π² ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΡŽ q0an, Π΄Π°Π»Π΅Π΅ примСняСтся ΠΊΠΎΠΌΠ°Π½Π΄Π° (n), ΠΈ ΠΌΠ°ΡˆΠΈΠ½Π° T0 остановится.

Π’Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ, машина T0 ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌΠ° ΠΊ ΠΊΠΎΠ΄Π°ΠΌ нСсамопримСнимых машин Π’ ΠΈ Π½Π΅ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌΠ° ΠΊ ΠΊΠΎΠ΄Π°ΠΌ самопримСнимых машин Π’.

Π’Π΅ΠΏΠ΅Ρ€ΡŒ ΠΏΡ€ΠΈΠΌΠ΅Π½ΠΈΠΌ ΠΌΠ°ΡˆΠΈΠ½Ρƒ T0 ΠΊ Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠΉ ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΈ q1ai. Π‘Π°ΠΌΠ° машина T0 являСтся Π»ΠΈΠ±ΠΎ самопримСнимой, Π»ΠΈΠ±ΠΎ нСсамопримСнимой. Если T0 самопримСнима, Ρ‚ΠΎ ΠΏΠΎ Π΄ΠΎΠΊΠ°Π·Π°Π½Π½ΠΎΠΌΡƒ ΠΎΠ½Π° Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ ΠΎΡΡ‚ановится, Π½Π°Ρ‡Π°Π² с q1ai, ΠΈ ΠΏΠΎΡ‚ΠΎΠΌΡƒ ΠΎΠ½Π° нСсамопримСнима. Если T0 нСсамопримСнима, Ρ‚ΠΎ ΠΏΠΎ Π΄ΠΎΠΊΠ°Π·Π°Π½Π½ΠΎΠΌΡƒ, ΠΎΠ½Π° останавливаСтся Ρ‡Π΅Ρ€Π΅Π· ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ число шагов, Π½Π°Ρ‡Π°Π² с q1aj, ΠΈ ΠΏΠΎΡ‚ΠΎΠΌΡƒ ΠΎΠ½Π° самопримСнима. ΠŸΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ ΠΏΡ€ΠΎΡ‚ΠΈΠ²ΠΎΡ€Π΅Ρ‡ΠΈΠ΅, ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ° самопримСнимости алгоритмичСски Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠ°, Ρ‡Ρ‚ΠΎ ΠΈ Ρ‚Ρ€Π΅Π±ΠΎΠ²Π°Π»ΠΎΡΡŒ Π΄ΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ.

ΠŸΡ€ΠΎΠ±Π»Π΅ΠΌΠ° остановки алгоритмичСски Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠ°, Ρ‚. ΠΊ. Ссли Π±Ρ‹ ΠΎΠ½Π° Π±Ρ‹Π»Π° Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠΉ, Ρ‚ΠΎ ΠΌΡ‹ ΠΏΠΎΠ»ΡƒΡ‡ΠΈΠ»ΠΈ Π±Ρ‹ Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΡΡ‚ΡŒ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ самопримСнимости.

Π’ ΠΌΠ°Ρ‚СматичСской Π»ΠΎΠ³ΠΈΠΊΠ΅ ΠΈ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠ² ΠΏΠΎΠ΄ Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΡΡ‚ΡŒΡŽ ΠΏΠΎΠ΄Ρ€Π°Π·ΡƒΠΌΠ΅Π²Π°ΡŽΡ‚ свойство Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΉ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΎΠ±Π»Π°Π΄Π°Ρ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΎΠΌ, ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΡΡŽΡ‰ΠΈΠΌ ΠΏΠΎ Π΄Π°Π½Π½ΠΎΠΉ Ρ„ΠΎΡ€ΠΌΡƒΠ»Π΅, Π²Ρ‹Π²ΠΎΠ΄ΠΈΠΌΠ° ΠΎΠ½Π° ΠΈΠ· ΠΌΠ½ΠΎΠΆΠ΅ΡΡ‚Π²Π° аксиом Π΄Π°Π½Π½ΠΎΠΉ Ρ‚Π΅ΠΎΡ€ΠΈΠΈ ΠΈΠ»ΠΈ Π½Π΅Ρ‚. ВСория называСтся Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠΉ, Ссли Ρ‚Π°ΠΊΠΎΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ сущСствуСт, ΠΈ Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠΉ, Π² ΠΏΡ€ΠΎΡ‚ΠΈΠ²Π½ΠΎΠΌ случаС.

Π˜ΠΌΠ΅Π΅Ρ‚ мСсто Π±Ρ‹Ρ‚ΡŒ ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π°Ρ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠ°: Π½Π΅ ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΠ΅Ρ‚ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° (ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°), ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‰Π΅Π³ΠΎ ΠΏΠΎ ΠΎΠΏΠΈΡΠ°Π½ΠΈΡŽ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΈ Π΅Π³ΠΎ исходных Π΄Π°Π½Π½Ρ‹Ρ… (ΠΈ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΈ Π΄Π°Π½Π½Ρ‹Π΅ Π·Π°Π΄Π°Π½Ρ‹ символами Π½Π° Π»Π΅Π½Ρ‚Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρ‹ Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°) ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, останавливаСтся Π»ΠΈ этот Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π½Π° ΡΡ‚ΠΈΡ… Π΄Π°Π½Π½Ρ‹Ρ… ΠΈΠ»ΠΈ Ρ€Π°Π±ΠΎΡ‚Π°Π΅Ρ‚ бСсконСчно.

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

Π’Π΅ΠΌ Π½Π΅ ΠΌΠ΅Π½Π΅Π΅, ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠΏΡ‹Ρ‚Π°Ρ‚ΡŒΡΡ ΡΡ„ΠΎΡ€ΠΌΡƒΠ»ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΡ€ΠΈΡ‡ΠΈΠ½Ρ‹, Π²Π΅Π΄ΡƒΡ‰ΠΈΠ΅ ΠΊ Π°Π»Π³ΠΎΡ€ΠΈΡ‚мичСской Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΡΡ‚ΠΈ, эти ΠΏΡ€ΠΈΡ‡ΠΈΠ½Ρ‹ достаточно условны, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ всС ΠΎΠ½ΠΈ сводимы ΠΊ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΠ΅ останова, ΠΎΠ΄Π½Π°ΠΊΠΎ Ρ‚Π°ΠΊΠΎΠΉ ΠΏΠΎΠ΄Ρ…ΠΎΠ΄ позволяСт Π±ΠΎΠ»Π΅Π΅ Π³Π»ΡƒΠ±ΠΎΠΊΠΎ ΠΏΠΎΠ½ΡΡ‚ΡŒ ΠΏΡ€ΠΈΡ€ΠΎΠ΄Ρƒ алгоритмичСской Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΡΡ‚ΠΈ:

  • Π°) ΠžΡ‚ΡΡƒΡ‚ΡΡ‚Π²ΠΈΠ΅ ΠΎΠ±Ρ‰Π΅Π³ΠΎ ΠΌΠ΅Ρ‚ΠΎΠ΄Π° Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ Π·Π°Π΄Π°Ρ‡ΠΈ
  • Π±) Π˜Π½Ρ„ΠΎΡ€ΠΌΠ°Ρ†ΠΈΠΎΠ½Π½Π°Ρ Π½Π΅ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΡΡ‚ΡŒ Π·Π°Π΄Π°Ρ‡ΠΈ
  • Π²) ЛогичСская Π½Π΅Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΡΡ‚ΡŒ (Π² ΡΠΌΡ‹ΡΠ»Π΅ Ρ‚Π΅ΠΎΡ€Π΅ΠΌΡ‹ ГёдСля ΠΎ Π½Π΅ΠΏΠΎΠ»Π½ΠΎΡ‚Π΅)
ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΡŒ вСсь тСкст
Π—Π°ΠΏΠΎΠ»Π½ΠΈΡ‚ΡŒ Ρ„ΠΎΡ€ΠΌΡƒ Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΉ Ρ€Π°Π±ΠΎΡ‚ΠΎΠΉ