матичний еквівалент для загального інтуїтивного уявлення про алгоритм. Це поняття названо по імені англійського математика, який сформулював його в 1937 р, за 9 років до появи першої електронно-обчислювальної машини.
Машина Тьюринга є математична (уявна) машина, а не машина фізична. Вона є такий же математичний об'єкт, як функція, похідна, інтеграл, група і. т.д. І, так само як і інші математичні поняття, поняття машини Тьюринга відображає об'єктивну реальність, моделює певні реальні процеси. Саме Тьюринг зробив спробу змоделювати дії математика (або іншої людини), що здійснює якусь розумову творчу діяльність. Така людина, перебуваючи в певному «умонастрої» («стані»), переглядає деякий текст. Потім він вносить у цей текст якісь зміни, переймається новим «умонастроєм» і переходить до перегляду наступних записів.
Машина Тьюринга діє приблизно так само. Її зручно представляти у вигляді автоматично працюючого пристрою. У кожен дискретний момент часу пристрій, перебуваючи в деякому стані, оглядає вміст однієї комірки, простягаємо через пристрій стрічки і робить крок, що полягає в тому, що пристрій переходить в новий стан, змінює (або залишає без зміни) вміст оглядається осередку і переходить до огляду наступної комірки - праворуч або ліворуч. Причому крок здійснюється на підставі запропонованої команди. Сукупність усіх команд являє собою програму машини Тьюринга.
Наведемо тепер машину Тьюринга більш ретельно. Машина розташовує кінцевим числом знаків (символів, букв), які утворюють так званий зовнішній алфавіт А={,, ...,}. У кожну клітинку оглядається стрічки в кожен дискретний момент часу може бути записаний тільки один символ з алфавіту А. Заради однаковості зручно вважати, що серед букв зовнішнього алфавіту А мається «порожня буква», і саме вона записана в порожню комірку стрічки. Домовимося, що «порожній буквою» або символом порожнього вічка є буква. Стрічка передбачається необмеженої в обидві сторони, але в кожен момент часу на ній записано кінцеве число непустих букв.
Далі, в кожен момент часу машина здатна перебувати в одному стані з кінцевого числа внутрішніх станів, сукупність яких Q={,, ...,}. Серед станів виділяються два - початкове і завершальне (або стан зупинки). Перебуваючи в стані, машина починає працювати. Потрапивши в стан, машина зупиняється.
Робота машини визначається програмою (функціональною схемою). Програма складається з команд. Кожна команда Т (i, j) (i=1,2, ..., m; j=0,1, ..., n) являє собою вираження одного з наступних видів:
gt; С; gt; П; gt; Л,
де 0? k? m; 0? ? ? n. У виразах першого виду символ З будемо часто опускати.
Як же працює машина Тьюринга? Перебуваючи в який-небудь момент часу в незаключітельном стані (тобто в стані, відмінному від), машина здійснює крок, який повністю визначається її поточним станом і символом, сприйманим нею в даний момент на стрічці. При цьому зміст кроку регламентовано відповідною командою Т (i, j): gt; X, де Х {С, П, Л}. Крок полягає в тому, що:
) вміст оглядається на стрічці осередку стирається і на його місце записується символ (який може збігатися з
) машина переходить у новий стан (воно також може збігатися з попередньому станом);
) машина переходить до огляду наступної правої комірки від тієї, яка обдивлялася тільки що, якщо Х=П, або до огляду наступної лівого вічка, якщо Х=Л, або ж продовжує оглядати ту ж комірку стрічки, якщо Х=С.
У наступний момент часу (якщо?) машина робить крок, регламентований командою Т (k, l):? Х і т.д.
Оскільки робота машини, за умовою, повністю визначається її станом в даний момент і вмістом оглядається в цей момент осередку, то для кожних і (i=1, 2, ..., m; j=0, 1 , ..., n) програма машини повинна містити одну і тільки одну команду, що починається символами. Тому програма машини Тьюринга із зовнішнім алфавітом А={,, ...,} і алфавітом внутрішніх станів Q={,, ...,} містить m (n + 1) команд.
Словом в алфавіті А або в алфавіті Q, або в алфавіті AQ називається будь-яка послідовність літер відповідного алфавіту. Під k-й конфігурацією будемо розуміти зображення стрічки машини з інформацією, що склалася на ній до початку k-го кроку (або слово в алфавіті А, записане на стрічку до початку k-го кроку), із зазначенням того, яка осередок обозревается в цей крок і в якому стані знаходиться машина. Мають сенс лише кінцеві конфігурації, тобто такі, в яких всі осередки стрічки, за винятком, можливо, кінцевого числа, порожні. Конфігурація називається заключній, якщо стан, в якому при цьому знаходиться машина, заключне.
Якщо вибрати яку-небудь незаключітельную конфігурацію машини Тьюринга...
