Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.

ΠŸΠΎΠ»ΡƒΡ‡ΠΈΡ‚ΡŒ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½Π½ΡƒΡŽ Ρ€Π°Π±ΠΎΡ‚Ρƒ ΠΈΠ»ΠΈ ΠΊΠΎΠ½ΡΡƒΠ»ΡŒΡ‚Π°Ρ†ΠΈΡŽ спСциалиста ΠΏΠΎ Π²Π°ΡˆΠ΅ΠΌΡƒ ΡƒΡ‡Π΅Π±Π½ΠΎΠΌΡƒ ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Ρƒ
Π£Π·Π½Π°Ρ‚ΡŒ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ

Алфавит – ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ ΠΈΠ»ΠΈ счСтноС мноТСство символов, Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ, Ρ€Π°Π·Π±ΠΈΡ‚Ρ‹Ρ… Π½Π° Π³Ρ€ΡƒΠΏΠΏΡ‹. Алфавит Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±Ρ‹Ρ‚ΡŒ упорядочСнным мноТСством.

Π‘Π»ΠΎΠ²ΠΎ – конСчная упорядочСнная ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ символов Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°, Π² Ρ‚.Ρ‡. пустоС слово.

V – мноТСство всСх слов.

Вычислимая функция ΠΎΡ‚ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… Π½Π°Ρ‚ΡƒΡ€Π°Π»ΡŒΠ½Ρ‹Ρ… ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Ρ… Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.

( f – ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ Π½Π΅ Π²ΡΡŽΠ΄Ρƒ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΉ )

f – называСтся вычислимой, Ссли Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния. такая машина Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°, которая Π΅Ρ‘ вычисляСт.

 

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β - Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠ΅ мноТСство, Ссли характСристичСская функция

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β - являСтся вычислимой.

ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния. называСтся пСрСчислимым, Ссли Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния. такая вычислимая функция

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.

М - Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎ Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния. М ΠΈ N \M пСрСчислимы.

М – пСрСчислимо Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния. М – ΠΎΠ±Π»Π°ΡΡ‚ΡŒ опрСдСлСния Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ вычислимой Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΈ.

ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ всСх Ρ„ΠΎΡ€ΠΌΡƒΠ» F – Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠ΅ подмноТСство V.

Π’ – счСтноС мноТСство, Ссли Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β Π΅Π³ΠΎ Π±ΠΈΠ΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΠ΅ ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π½Π° V.

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β - ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ счСтного мноТСства. (Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β - Π°Π»Π΅Ρ„-Π½ΡƒΠ»ΡŒ)

 

Если Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β ΠΈ зафиксировано Π±ΠΈΠ΅ΠΊΡ‚ΠΈΠ²Π½ΠΎΠ΅ ΠΈ вычислимоС ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β (вычис.),

Ρ‚ΠΎ L – ансамбль.

V – ансамбль (слова лСксикографичСски упорядочСны ΠΈ Π·Π°Π½ΡƒΠΌΠ΅Ρ€ΠΎΠ²Π°Π½Ρ‹)

 

ΠžΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅: Π’ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½ΠΎΠΌ Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΠΌ исчислСнии: Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β - мноТСство всСх аксиом – Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎΠ΅ подмноТСство мноТСства всСх Ρ„ΠΎΡ€ΠΌΡƒΠ».

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.

ΠŸΡ€Π°Π²ΠΈΠ»ΠΎ Π²Ρ‹Π²ΠΎΠ΄Π°:

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β  ,ΠΏΡ€ΠΈ Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β Ρ€Π°Π·Ρ€Π΅ΡˆΠΈΠΌΠΎ. Для Π˜Π’ N=2.

ΠŸΡ€ΠΈΠΌΠ΅Ρ€:

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β Β Β Β  Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β (пустоС слово)Β  , Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.

Π€ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ исчислСния.Β Β  1 ΠΈ 2 – Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Π²Ρ‹Π²ΠΎΠ΄Ρ‹.

Β Β  3 – Π½Π΅ являСтся Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΌ Π²Ρ‹Π²ΠΎΠ΄ΠΎΠΌ.

 

 

Π’Π½ΠΈΠΌΠ°Π½ΠΈΠ΅!
Если Π²Π°ΠΌ Π½ΡƒΠΆΠ½Π° ΠΏΠΎΠΌΠΎΡ‰ΡŒ Π² написании Ρ€Π°Π±ΠΎΡ‚Ρ‹, Ρ‚ΠΎ Ρ€Π΅ΠΊΠΎΠΌΠ΅Π½Π΄ΡƒΠ΅ΠΌ ΠΎΠ±Ρ€Π°Ρ‚ΠΈΡ‚ΡŒΡΡ ΠΊ профСссионалам. Π‘ΠΎΠ»Π΅Π΅ 70 000 Π°Π²Ρ‚ΠΎΡ€ΠΎΠ² Π³ΠΎΡ‚ΠΎΠ²Ρ‹ ΠΏΠΎΠΌΠΎΡ‡ΡŒ Π²Π°ΠΌ прямо сСйчас. БСсплатныС ΠΊΠΎΡ€Ρ€Π΅ΠΊΡ‚ΠΈΡ€ΠΎΠ²ΠΊΠΈ ΠΈ Π΄ΠΎΡ€Π°Π±ΠΎΡ‚ΠΊΠΈ. Π£Π·Π½Π°ΠΉΡ‚Π΅ ΡΡ‚ΠΎΠΈΠΌΠΎΡΡ‚ΡŒ своСй Ρ€Π°Π±ΠΎΡ‚Ρ‹.