Tyuring mashinasining ishlashi

Raqamlar to'plamini raqamlash
Algoritmlar nazariyasida bir nechta o'zgaruvchining funktsiyalarini o'rganishni bitta o'zgaruvchining funktsiyalarini o'rganishga qisqartirish imkonini beradigan texnika keng tarqaldi. U raqamlar to'plamini sanab o'tishga asoslanadi, shunda raqamlar to'plami va ularning raqamlari o'rtasida ikki tomonlama muvofiqlik mavjud bo'ladi va uning sonini raqamlar to'plamidan va raqamlar to'plamining sonidan aniqlaydigan funktsiyalar umumiy rekursivdir. . Misol uchun, ikkita mustaqil o'zgaruvchini (x, y) o'z ichiga olgan funktsiya uchun h(x, y) xaritasi quyidagicha ko'rinishi mumkin:
1-rasm.
(x, y) juftlari qisman tartiblangan N (2) to'plamni tashkil etsin. h(x, y) = n berilgan bo'lsa, u holda teskari xaritalash mavjud: x = h -1 1 (n) va y= h -1 2 (n), ya'ni h(h -1 1 (n), h - 1 2 (n)) = n. Bu har qanday juftlik (x, y) uchun n sonini hisoblash va aksincha, n sonidan x va y qiymatlarini hisoblash imkonini beradi:

Ushbu qoidalardan foydalanib, h 2 (x, y, z) = h (h (x, y), z) = n uchliklarining raqamlanishini va aksincha, uchlik soni bo'yicha - x qiymatlarini hisoblash mumkin. , y, z. Masalan, h 2 (x, y, z) = n bo'lsa, z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ), h -1 2 (n)). Uchlik (x, y, z) qisman tartiblangan N (3) to'plamni hosil qiladi. Xuddi shunday, ixtiyoriy sonli raqamlar uchun bizda:
h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Agar h n-1 (x1, x2,…, xn)=m bo'lsa, xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ................................, x2 = h -1 2 (h -1 1 (... h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).
N (1) , N (2) ,..., N (i) ,..., N(n) toʻplamlari raqamlanishiga ega boʻlgan holda, bu yerda N (i) (i) sonlar toʻplami, M = N (1) N (2) ... N (i) .. N(n) , bu erda M N. Har qanday n N uchun bizda h(x1,x2, ..., xn )= h(h n −1 (x1,x2,..., xn), n −1).
Agar h(x ,1x ,2..., x)n = m, u holda h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Yuqoridagi formulalar yordamida siz x1, x2,…, xn qiymatlarini tiklashingiz mumkin.