2021, випуск 2, c. 63-67
Одержано 06.05.2021; Виправлено 12.05.2021; Прийнято 24.06.2021
Надруковано 30.06.2021; Вперше Online 01.07.2021
https://doi.org/10.34229/2707-451X.21.2.6
Попередня | Повний текст | Наступна
Методи нумерації дискретних послідовностей
М.А. Гупал
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Нумерація, або кодування, дискретних послідовностей відіграють фундаментальну роль у теорії розпізнавання та обчисленності. За допомогою кодування отримують коди або індекси програм та обчислених функцій. Встановлено, що існують універсальні програми, тобто програми, які реалізують усі інші програми. Це один з основних результатів в теорії обчисленності. На основі нумерації дискретних послідовностей Гедель довів відому теорему про неповноту арифметики.
Мета роботи. Розробити взаємно однозначні нумерації натуральними числами скінченних диск-ретних послідовностей, програм та обчислювальних функцій.
Результати. На основі нумерацій скінченних дискретних послідовностей побудовано нумерації для чотирьох команд машини з необмеженими регістрами (МНР) в натуральні числа виду 4u, 4u +1, 4u+2, 4u+3 відповідно. Кожна програма складається з скінченого списку команд. На основі бієкцій для чотирьох команд МНР визначено взаємно однозначні нумерації для усіх програм МНР. Таким чином, на основі заданої програми P можна ефективно знайти її кодовий номер γ(P), і навпаки, на основі заданого номера n можна ефективно знайти програму Pn = γ–1(n).
Висновки. Розроблено взаємно однозначні нумерації натуральними числами скінчених дискретних послідовностей, програм для МНР та обчислених функцій. Спираючись на нумерацію програм у теорії обчислених функцій встановлено, що існують універсальні програми, тобто програми, які реалізують усі інші програми. На основі обчисленності універсальних функцій та s-m-n теореми встановлено на-ступні операції для функцій: комбінація φx та φy, яка дає добуток φxφy, операція перетворення функцій, операція рекурсії.
Ключові слова: нумерація, геделев кодовий номер, діагональний метод.
Цитувати так: Гупал М.А. Методи нумерації дискретних послідовностей. Cybernetics and Computer Technologies. 2021. 2. С. 63–67. https://doi.org/10.34229/2707-451X.21.2.6
Список літератури
1. Shepherdson J.C., Sturgis H.E. Computability of recursive functions. J. Assoc. Comput. Machinery. 1963. 10 (2). P. 217–255. https://doi.org/10.1145/321160.321170
2. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972. 624 с.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | Повний текст | Наступна