Ім'я файлу: 20 задание.docx
Розширення: docx
Розмір: 20кб.
Дата: 10.12.2021
скачати
Пов'язані файли:
Футбол - оцінка псих підготовки..docx
Розширення: docx
Розмір: 20кб.
Дата: 10.12.2021
скачати
Пов'язані файли:
Футбол - оцінка псих підготовки..docx
1.3. Які дії виконує машина Тюрінга працюючи згідно зі схемою:
Машина Тюрінга – це строга математична побудова, математичний апарат, створений для розв’язування певних задач. Цей математичний апарат був названий «машиною» з тієї причини, що за описом його складових частин і функціонування він схожий на обчислювальну машину. Принципова відмінність машини Тюрінга від обчислювальних машин полягає в тому, що її блок зовнішньої пам’яті нескінченною стрічкою: у реальних обчислювальних машин запам’ятовуючий пристрій може бути як завгодно великим, але обов’язково скінченним. Машину Тюрінга не можна реалізувати саме через нескінченність її стрічки. У цьому сенсі вона потужніша від будь-якої обчислювальної машини.
Конкретна машина Тьюринга задається перерахуванням елементів безлічі букв алфавіту A, безлічі станів Q і набором правил, за якими працює машина. Вони мають вигляд: qiaj → qi1 aj1 dk (якщо головка знаходиться в стані qi, а в оглядається осередку записана буква aj, то головка переходить в стан qi1, в клітинку замість aj записується aj1, головка робить рух dk, яке має три варіанти: на осередок вліво (L), на осередок вправо (R), залишитися на місці (N)).
Приклад машини Тьюринга для множення чисел в унарною системі числення. Запис правила «qiaj → qi1 aj1 R / L / N» слід розуміти так: qi - стан при якому виконується це правило, aj - дані в осередку, в якій знаходиться головка, qi1 - стан в яке потрібно перейти, aj1 - що потрібно записати в осередок, R / L / N - команда на переміщення.
Розглянемо як машина Тьюринга буде виконувати дану схему:
Згідно схеми, машина Тьюринга має лише два режими роботи: q0 – при якому вона буде в стані спокою та q1 – режим із заданим правилом. Спочатку машина Тюрінга знаходиться в режимі q0 – в стані спокою, тобто зупинена, потім вона перейде в режим роботи q1, який заданий декількома правилами.
Перше правило – якщо дане в осередку 0, то голівка замінить його на 1 та виконає переміщення на одну клітинку праворуч.
Друге правило – якщо дане в осередку 1, то голівка залишить значення даного незмінним та машина Тьюринга завершить свою роботу.
Тобто конкретно в даному випадку при введенні послідовності 0 і 1, 0 будуть змінюватися на 1 поки голівка не виявить в клітинці 1, тоді машина буде зупинена.
Приклад: введено послідовність 000010. Першим нуль буде замінено на 1 та голівка пересунеться на клітинку праворуч, тобто на наступну цифру послідовності. Так буде продовжуватися поки голівка не виявить 1, тоді процес буде зупинено. В даному випадку ми отримає таку послідовність: 111110.