Машина Т’юринга

Назва, що закріпилася за абстрактними обчислювальними машинами деякого точно охарактеризованого типу. Концепція такого роду машини виникла в середині 30-х рр. 20-го століття у А.М. Т’юринга внаслідок проведеного ним аналізу дій людини, яка виконує відповідно до заздалегідь розробленого плану ті або інші обчислення, тобто послідовні пере- творення знакових комплексів. Аналіз цей, у свою чергу, був здійснений ним з метою вирішення назрілої на той час проблеми пошуку точного математичного еквівалента для загального інтуїтивного уявлення про алгоритм.

В ході розвитку теорії алгоритмів з’явився ряд модифікацій первинного т’юринговського визначення. Машину Т’юринга зручно уявляти собі у вигляді автоматично функціонуючого пристрою, здатного знаходитися в кінцевому числі внутрішніх станів і забезпеченого нескінченною зовнішньою пам’яттю – стрічкою. Серед станів є два виділених – початкове і завершальне. З концепції машини Т’юринга витікають всі найважливіші поняття інформаційних технологій: реалізація алгоритму, програма й елемент програми – команда.