Машина Тюрінга як модель обчислень: теоретичні основи та сучасні інтерпретації

Автор(и)

  • С. О. Головня Донецький національний університет імені Василя Стуса
  • О. А. Павлюк Донецький національний університет імені Василя Стуса

Анотація

Проблема формального визначення алгоритму є центральною в розвитку теорії обчислень. Щоб описати процес обчислення у строгих математичних термінах, потрібна універсальна модель, здатна відтворювати будь-які логічні та арифметичні дії. Таку модель у 1936 р. запропонував Алан Тюрінг, створивши абстрактну машину Тюрінга. У своїй праці «On Computable Numbers…» він визначив поняття обчислюваних чисел і довів, що не існує універсального алгоритму, який може встановити істинність будь-якого математичного твердження, тобто проблема розв’язності (Entscheidungsproblem) не має загального рішення [1]. Запропонована модель стала підґрунтям тези Черча–Тюрінга, згідно з якою будьякий ефективний алгоритм може бути реалізований у межах машини Тюрінга [1], [2]. Ця ідея визначила сучасне розуміння процесу обчислень і меж можливого в алгоритмах.

Біографії авторів

С. О. Головня , Донецький національний університет імені Василя Стуса

здобувачка 2 курсу спеціальності 122 Комп’ютерні науки

О. А. Павлюк , Донецький національний університет імені Василя Стуса

канд. техн. наук, старший викладач кафедри інформаційних технологій

Посилання

1. Тюрінг А. М. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society. 1937. Vol. 42. P. 230–265.

2. Новаторський М. А. Алгоритми та методи обчислень. Київ: КПІ ім. Ігоря Сікорського, 2019. 256 с.

3. Ящик О. Б. Машина Тюрінга як універсальний виконавець алгоритмів та її застосування в процесі поглибленого вивчення алгоритмізації і основ програмування. Інформаційні технології і засоби навчання. 2016. Т. 52, № 2. С. 10–16.

Завантаження

Опубліковано

2026-11-20