13-ma'ruza. Np bilan bog'liq muammolar. Hisoblash qobiliyatsizligi Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna Reja

To'xtatish muammosi.

Ixtiyoriy algoritm (uning raqami) va manbali ma'lumotlarning tavsifiga ko'ra (algoritm va Turing mashinasi lentasida berilgan ma'lumotlar) ushbu algoritm ushbu ma'lumotlarning to'xtashini yoki doimiy ravishda ishlashini cheklashga imkon beradigan algoritm (Turing mashinasi) mavjud emas.

Algoritmlar nazariyasida o'z-o'zini qo'llash (to'xtash muammosining alohida holati) - bu algoritmning rasmiy yozuvini aks ettiruvchi ma'lumotlarga shoshilinch ravishda javob beradigan algoritmning xususiyatidir.

O'z-o'zidan qo'llaniladigan algoritmga misol: A alifboda bir xil simli o'zgarishlar.

Teorema O'z-o'zini qo'llash muammosini hal qiladigan Turing Machine yo'q. Turing mashinalari uchun tashqi alfavit sifatida A = {0,1} ni olamiz. Biz aytamizki, MT o'z-o'zidan qo'llanilishi muammosini hal qiladi, agar biron bir T mashinasi uchun konfiguratsiya q 01 Kod (T) bo'lsa, u q01 konfiguratsiyasiga, agar T o'z-o'ziga mos kelmasa q00 konfiguratsiyasiga aylanadi.

Isbot.

Aytaylik, o'z-o'zini qo'llash muammosini hal qiladigan "Mashina" bor. Biz T1 mashinasini quramiz, unda shtatning o'rniga biz yangi yakuniy holat rrini kiritamiz va mashina dasturiga yangi buyruqlar qo'shamiz.

• q01 -> p01E, (halqa)

• p00-> gr 0E (*)

T1 mashinasi To Mashinada juda konstruktiv usulda yaratilgan va qo'llanilmaydigan mashinalarning kodlariga nisbatan qo'llaniladi va o'z-o'zidan ishlaydigan mashinalarning kodlariga qo'llanilmaydi. Bunday mashinaning mavjudligi qarama-qarshilikka olib keladi, chunki T1 o'z-o'zidan yoki o'z-o'zidan qo'llanilishi mumkin emas. Darhaqiqat, agar T1 o'z-o'zidan qo'llanilsa, q 1 Kod (T) qo1 ga kiradi va go1E va T1 qoida (*) ga muvofiq hech qachon to'xtamaydi, ya'ni. qurilish orqali, u o'z-o'zidan qo'llaniladigan mashinalarning kodiga taalluqli emas. Agar T1 o'z-o'zidan qo'llanmasa, q1 kod (T1) qo0 ga kiradi va (*) qo0 ga binoan prO va T1 ga to'xtaydi, ya'ni. qurilish orqali, u o'z yozuvida qo'llaniladi, chunki u qo'llanilmaydigan mashinaning har qanday yozuviga nisbatan qo'llaniladi va bu shunchaki T1 o'z-o'zidan qo'llanilishini anglatadi. Biz qarama-qarshilikka erishdik, ya'ni. O'z-o'zini qo'llash muammosini hal qiladigan MT mavjudligi to'g'risidagi taxmin noto'g'ri. Tyuring tezisiga ko'ra, MTni qurish mumkin emasligi bu muammoni hal qilish uchun algoritm yo'qligini anglatadi.