Т'юринга машина, назва, що закріпилася за абстрактними (уявними) «обчислювальними машинами» деякого точно охарактеризованого типа, що дають придатне для цілей математичного розгляду уточнення загального інтуїтивного уявлення про алгоритмі . Концепція такого роду машини склалася в середині 30-х рр. 20 ст в А. М. Т'юринга в результаті виробленого їм аналізу дій людини, що виконує відповідно до заздалегідь розробленого плану ті або інші обчислення, тобто послідовні перетворення знакових комплексів.
Т. м. зручно представляти у вигляді деякого пристрою, що автоматично діє, здатного знаходитися в кінцевому числі внутрішніх станів і забезпеченого безконечною зовнішньою пам'яттю — стрічкою. Серед станів є два виділених — початкове і завершальне. Стрічка розділена на клітки (вічка) і не обмежена вліво і управо. У кожній клітці стрічки може бути записаний будь-яким з символів, що входять в деякий заздалегідь заданий перелік (ради одноманітності вважають, що в порожній клітці записана «порожня буква»). У кожен момент часу Т. м. знаходиться в одному зі своїх станів і, розглядаючи (за допомогою спеціального пристрою) одну з кліток своєї стрічки, сприймає записаний в ній символ. Якщо у нинішній момент часу Т. м. знаходиться в не завершальному стані, то в наступний за ним момент: 1) вона переходить в новий стан, мабуть співпадаючий із старим, або завершальне; 2) у даній клітці старий символ замінюється новим, мабуть порожнім або співпадаючим із старим; 3) стрічка машини зрушується на одну клітку вліво або управо або залишається на місці. Цей крок Т. м. сповна визначається її поточним станом і поточним сприйманим символом. Таблиця, що містить повне перерахування можливих кроків даною Т. м., називається програмою цієї машини.
Поточний повний опис Т. м. дається її конфігурацією, яка складається з вказівки для даного моменту наступної інформації: 1) конкретного заповнення кліток стрічки символами, 2) клітки, що знаходиться у полі зору машини, 3) стану, в якому машина знаходиться.
Якщо в даної Т. м. взяти за початкову яку-небудь конфігурацію з не завершальним станом, то робота цієї машини полягатиме в послідовному, крок за кроком, перетворенні вихідної конфігурації відповідно до програми машини до тих пір, поки не буде досягнута конфігурація із завершальним станом. Ета остання, якщо вона існує, і вважається результатом роботи даною Т. м. над вихідною конфігурацією.
Є серйозні підстави вважати, що поняття Т. м. доставляє адекватне уточнення загального уявлення про алгоритм, тобто що всякий алгоритм може бути промоделірован відповідною Т. м. Відповідна угода відома в алгоритмів теорії під назвою тези Т'юринга. Теорія Т. м. дає зручний робочий апарат для багатьох досліджень, що вимагають точного поняття алгоритму. Зокрема, зважаючи на природність здійснюваних ними кроків, Т. м. стали об'єктом пильної уваги в теорії складності алгоритмічних обчислень. В ході розвитку теорії Т. м. розглядалися різні їх узагальнення: наприклад, Т. м. із загальнішим типом стрічок, з декількома стрічками, а також недетерміновані Т. м.
Літ.: Кліні С. До., Введення в метаматематику, пер.(переведення) з англ.(англійський), М., 1957; Мендельсон Е., Введення в математичну логіку, пер.(переведення) з англ.(англійський), М., 1971.
