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

Попередня  |  Повний текст  |  Наступна

 

УДК 519.272.2

Методи нумерації дискретних послідовностей

М.А. Гупал

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути 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)

Попередня  |  Повний текст  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2022,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.