Машина тьюринга паскаль

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Машины Тьюринга
Люди добрые, подскажите пожалуйста, а то завтра на зачет идти по Математической Логике) На.

состояние Машины Тьюринга
Помогите, пожалуйста/ 1. Сначала мне казалось что это номер ячейки на ленте, но я встретила.

Программа машины Тьюринга
A=<0, 1, 2, 3>. Считая непустое слово P записью числа в четыричной системе счисления, получить.

Машины Тьюринга — обозначения
Я привык, что если машина Тьюринга занимается арифметикой, то натуральное число x на её ленте.

Машины Тьюринга

Зачем нужны простые вычислительные модели?

До сих пор нам было удобно ссылаться на программистский опыт , говоря об алгоритмах, программах, интерпретаторах, пошаговом выполнении и т.д. Это позволяло нам игнорировать детали построения тех или иных алгоритмов под тем предлогом, что читатель их легко восстановит (или хотя бы поверит все-таки не каждый читатель в своей жизни писал интерпретатор паскаля на паскале).

Но в некоторых случаях этого недостаточно. Пусть, например, мы хотим доказать алгоритмическую неразрешимость какой-то задачи, в определении которой ничего не говорится о программах (в этом разделе, например, мы докажем неразрешимость проблемы равенства слов в полугруппах , заданных образующими и соотношениями). Это обычно делается так. Мы показываем, что проблема остановки сводится к этой задаче. Для этого мы моделируем работу произвольного алгоритма в терминах рассматриваемой задачи (что это значит, будет видно из приводимого ниже примера). При этом нам важно, чтобы определение алгоритма было как можно проще.

Таким образом, наш план таков. Мы опишем довольно просто определяемый класс машин (его можно выбирать по-разному, мы будем использовать так называемые машины Тьюринга), затем объявим, что всякая вычислимая функция может быть вычислена на такой машине, а затем покажем, что вопрос об остановке машины Тьюринга можно свести к вопросу о равенстве слов в полугруппе.

Другая причина, по которой важны простые вычислительные модели (таких моделей много разные виды машин Тьюринга, адресные машины и т.п.), связана с теорией сложности вычислений, когда нас начинает интересовать время выполнения программ. Но этот вопрос выходит за рамки классической теории алгоритмов.

Машины Тьюринга: определение

Машина Тьюринга имеет бесконечную в обе стороны ленту, разделенную на квадратики ( ячейки ). В каждой ячейке может быть записан некоторый символ из фиксированного (для данной машины) конечного множества , называемого алфавитом данной машины. Один из символов алфавита выделен и называется » пробелом» предполагается, что изначально вся лента пуста, то есть заполнена пробелами.

Машина Тьюринга может менять содержимое ленты с помощью специальной читающей и пишущей головки, которая движется вдоль ленты. В каждый момент головка находится в одной из ячеек. Машина Тьюринга получает от головки информацию о том, какой символ та видит, и в зависимости от этого (и от своего внутреннего состояния) решает, что делать, то есть какой символ записать в текущей ячейке и куда сдвинуться после этого (налево, направо или остаться на месте). При этом также меняется внутреннее состояние машины (мы предполагаем, что машина не считая ленты имеет конечную память , то есть конечное число внутренних состояний). Еще надо договориться, с чего мы начинаем и когда кончаем работу.

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

• произвольное конечное множество A ( алфавит ); его элементы называются символами ;
• некоторый выделенный символ ( пробел, или пустой символ );
• конечное множество S , называемое множеством состояний ;
• некоторое выделенное состояние , называемое начальным ;
• таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа (см. ниже);
• некоторое подмножество , элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

Таблица переходов устроена следующим образом: для каждой пары указана тройка . Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A -> S x A x <-1,0,1>, определенная на тех парах, в которых состояние не является заключительным.

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z -> A ), текущей позиции головки (некоторое целое число ) и текущего состояния машины (элемент S ). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом, если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово , которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1 ).

Таким образом, любая машина Тьюринга задает некоторую частичную функцию на двоичных словах. Все такие функции естественно назвать вычислимыми на машинах Тьюринга.

Машины Тьюринга: обсуждение

Разумеется, наше определение содержит много конкретных деталей, которые можно было бы изменить. Например, лента может быть бесконечной только в одну сторону. Можно придать машине две ленты. Можно считать, что машина может либо написать новый символ, либо сдвинуться, но не то и другое вместе. Можно ограничить алфавит , считая, скажем, что в нем должно быть ровно 10 символов. Можно потребовать, чтобы в конце на ленте ничего не было, кроме результата работы (остальные клетки должны быть пусты). Все перечисленные и многие другие изменения не меняют класса вычислимых на машинах Тьюринга функций. Конечно, есть и небезобидные изменения. Например, если запретить машине двигаться налево, то это радикально поменяет дело по существу лента станет бесполезной, так как к старым записям уже нельзя будет вернуться.

Как понять, какие изменения безобидны, а какие нет? Видимо, тут необходим некоторый опыт практического программирования на машинах Тьюринга, хотя бы небольшой. После этого уже можно представлять себе возможности машины, не выписывая программы полностью, а руководствуясь лишь приблизительным описанием. В качестве примера опишем машину, которая удваивает входное слово (изготавливает слово XX , если на входе было слово X ).

Если машина видит пробел ( входное слово пусто), она кончает работу. Если нет, она запоминает текущий символ и ставит пометку (в алфавите помимо символов 0 и 1 будут еще их » помеченные варианты» и ). Затем она движется направо до пустой клетки, после чего пишет там копию запомненного символа. Затем она движется налево до пометки; уткнувшись в пометку, отходит назад и запоминает следующий символ и так далее, пока не скопирует все слово .

Имея некоторый опыт , можно за всеми этими фразами видеть конкретные куски программы для машины Тьюринга. Например, слова » запоминает символ и движется направо» означают, что есть две группы состояний, одна для ситуации, когда запомнен нуль, другая когда запомнена единица , и внутри каждой группы запрограммировано движение направо до первой пустой клетки.

Имея еще чуть больше опыта, можно понять, что в этом описании есть ошибка не предусмотрен механизм остановки, когда все слово будет скопировано, поскольку копии символов ничем не отличаются от символов исходного слова. Ясно и то, как ошибку исправить надо в качестве копий писать специальные символы и , а на последнем этапе все пометки удалить.

77. Покажите, что функция » обращение», переворачивающая слово задом наперед, вычислима на машине Тьюринга.

Другой пример неформального рассуждения: объясним, почему можно не использовать дополнительных символов, кроме 0 , 1 и пустого символа. Пусть есть машина с большим алфавитом из N символов. Построим новую машину, которая будет моделировать работу старой, но каждой клетке старой будет соответствовать блок из k клеток новой. Размер блока (число k ) будет фиксирован так, чтобы внутри блока можно было бы закодировать нулями и единицами все символы большого алфавита. Исходные символы 0 , 1 и пустой будем кодировать как 0 , за которым идут (k-1) пустых символов, 1 , за которым идут (k-1) пустых символов, и группу из k пустых символов. Для начала надо раздвинуть буквы входного слова на расстояние k , что можно сделать без дополнительных символов (дойдя до крайней буквы, отодвигаем ее, затем дойдя до следующей, отодвигаем ее и крайнюю и так далее); надо только понимать, что можно идентифицировать конец слова как позицию, за которой следует более k пустых символов. Ясно, что в этом процессе мы должны хранить в памяти некоторый конечный объем информации, так что это возможно. После этого уже можно моделировать работу исходной машины по шагам, и для этого тоже достаточно конечной памяти (е конечного числа состояний), так как нам важна только небольшая окрестность головки моделируемой машины. Наконец, надо сжать результат обратно.

Утверждение о том, что всякая вычислимая функция вычислима на машине Тьюринга, называют тезисом Тьюринга. Конечно, его смысл зависит от того, что понимать под словами » вычислимая функция «. Если понимать их в расплывчато-интуитивном смысле (» функция вычисляется алгоритмически, то есть по четким, недвусмысленным, однозначным правилам» или что-то в таком роде), конечно, ни о каком доказательстве тезиса Тьюринга не может быть речи. Можно лишь говорить, что многовековая практика человечества от Евклида до Кнута не встретилась с примером алгоритма, который нельзя было бы записать как программу машины Тьюринга и т.п. Впрочем, еще один (не слишком убедительный) аргумент приведен ниже.

Но если понимать слово » вычислимая» в тезисе Тьюринга как » вычислимая с помощью программы на паскале» и представить себе на минуту, что синтаксис и семантика паскаль -программ точно определены, то тезис Тьюринга станет уже четким утверждением, которое может быть истинным или ложным, и которое можно доказывать. Конечно, такое доказательство по необходимости должно использовать формальное описание синтаксиса и семантики паскаля, и потому никем не проводилось, но для более простых вычислительных моделей это действительно можно формально доказать. Впрочем, такого рода доказательства сродни доказательству корректности длинной программы, и потому желающих их писать и тем более читать немного.

В заключение обсуждения приведем обещанный выше аргумент в пользу того, что любая вычислимая функция вычислима на машине Тьюринга. Пусть есть функция , которую человек умеет вычислять. При этом, он, естественно, должен использовать карандаш и бумагу, так как количество информации , которое он может хранить » в уме», ограничено. Будем считать, что он пишет на отдельных листах бумаги. Помимо текущего листа, есть стопка бумаг справа и стопка слева; в любую из них можно положить текущий лист , завершив с ним работу, а из другой стопки взять следующий. У человека есть карандаш и ластик. Поскольку очень мелкие буквы не видны, число отчетливо различимых состояний листа конечно, и можно считать, что в каждый момент на листе записана одна буква из некоторого конечного (хотя и весьма большого) алфавита. Человек тоже имеет конечную память , так что его состояние есть элемент некоторого конечного множества . При этом можно составить некоторую таблицу, в которой записано, чем кончится его работа над листом с данным содержимым, начатая в данном состоянии (что будет на листе, в каком состоянии будет человек и из какой пачки будет взят следующий лист ). Теперь уже видно, что действия человека как раз соответствуют работе машины Тьюринга с большим (но конечным) алфавитом и большим (но конечным) числом внутренних состояний.

Лабораторная работа «Разработка программ для машины Тьюринга»

Цель: научится строить машины Тьюринга на специальном тренажере для изучения универсального исполнителя.

Эмулятор машины Тьюринга

Что такое машина Тьюринга?

Машина Тьюринга — это универсальный исполнитель (абстрактная вычислительная машина), предложенный английским математиком А. Тьюрингом в 1936 году как уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга.

Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A = <a,a1,…,aN> . Любой алфавит содержит символ «пробел», который обозначается как a или L.

Машина Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = <q,q1,…,qM>. В начале работы машина Тьюринга находится в состоянии q1. Состояние q — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей

· символ из алфавита A

· направление перемещения: «>» (вправо), « 1

Задание 1.

Вариант 1

Вариант 2

Написать машину Тьюринга, которая исправляет ошибку в слове «пороллилагромм».

Написать машину Тьюринга, которая исправляет ошибку в слове «иксковотар».

Задание 2. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, т.е. выполняла функцию , при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа.

Состояние q1 — уменьшаем младшую (очередную) цифру на 1. Если она больше 1, то после уменьшения — сразу останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. Если уменьшаемая цифра равна 1, то вместо нее пишем 0 и переходим в состояние q2.

Состояние q2 — после записи “0” в каком-либо разряде надо проанализировать, не является ли этот ноль старшей незначащей цифрой (т.е. не стоит ли слева от него в записи выходного слова a0).

Состояние q3 — если записанный “0” является старшей незначащей цифрой, то его надо удалить из записи выходного слова.

Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.

Задание 3.

Вариант 1

Вариант 2

Реализовать на эмуляторе машины Тьюринга алгоритм вычисления функции .

Вычислите

Реализовать на эмуляторе машины Тьюринга алгоритм вычисления функции .

Вычислите

Задание 4. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.

Например, дано “) ( ( ) ( ( )”, надо получить “). ( ( ”.

Автомат в состоянии q1 обозревает крайний левый символ строки.

Ключ к заданию.

Задание 5. Оформите отчет, записав в него таблицы (программы) для машин Тьюринга из заданий №1, №3 и №4.

Содержимое разработки

Лабораторная работа №7

Тема: «Разработка программ для машины Тьюринга»

Цель: научится строить машины Тьюринга на специальном тренажере для изучения универсального исполнителя.

Эмулятор машины Тьюринга

Что такое машина Тьюринга?

Машина Тьюринга — это универсальный исполнитель (абстрактная вычислительная машина), предложенный английским математиком А. Тьюрингом в 1936 году как уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга.

Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A = <a,a₁,…,a_N> . Любой алфавит содержит символ «пробел», который обозначается как a или .

Машина Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = <q,q₁,…,q_M>. В начале работы машина Тьюринга находится в состоянии q₁. Состояние q — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу a_i и некоторому состоянию q_j, находится команда, состоящая из трех частей

 символ из алфавита A

 направление перемещения: « » (вправо), «» (влево) или «.» (на месте)

 новое состояние автомата

При вводе команд пробел заменяется знаком подчеркивания «_».

Как работать с программой?

В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты (или щелчком правой кнопкой мыши) можно изменить ее содержимое.

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к введенным символам автоматически.

В таблице в нижней части окна набирается программа. В первом столбце записаны символы алфавита, он заполняется автоматически. В первой строке перечисляются все возможные состояния. Добавить и удалить столбцы таблицы (состояния) можно с помощью кнопок, расположенных над таблицей.

При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если пропущен номер состояния, по умолчанию состояние автомата не изменяется.

Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению. Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.

Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи, алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи из файла и сохранении в файле состояние ленты автоматически записывается в буфер.

Пример 1. Написать машину Тьюринга, которая исправляет ошибку в слове «малако».

Запускаем программу turing.exe.

Вносим символы «аклмо» в алфавит программы.

На ленте начиная с позиции «0» вводим слово «малако».

Удаляем ненужные столбцы Q кнопкой .

Машина тьюринга паскаль

«Сами машины — это пустые перчатки, но их надевает человеческая рука, которая может быть хорошей или плохой»

Машина Тьюринга — это универсальная учебная машина, созданная для уточнения понятия алгоритм.

Первым из всех ученых идею универсального исполнителя предложил Алан Тьюринг (1936г.). Для уточнения понятия алгоритма, им был разработан абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.

Машина Тьюринга состоит из:

— бесконечной в обе стороны ленты, разделенной на ячейки;

— каретки (читающей и записывающей головки);

Программируемый автомат управляет кареткой, посылая ей команды в соответствии с заложенной в него сменяемой программой. Лента выполняет роль внешней памяти компьютера, автомат — роль процессора, а каретка служит для ввода и вывода данных.

Программа для машины Тьюринга

Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

Внешний алфавит. Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.

Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = <0, 1, а0>.

Непрерывную цепочку символов на ленте называют словом.

Автоматом называют устройство, работающее без участия человека. Автомат в машине Тьюринга имеет несколько состояний и при определенных условиях переходит из одного состояния в другое. Множество состояний автомата называют внутренним алфавитом.

Внутренний алфавит. Конечное множество состояний каретки (автомата). Обозначается буквой Q=. Одно из состояний — q1- должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка.

Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.

Автомат машины Тьюринга в процессе своей работы управляется программой, во время каждого шага которой выполняются последовательно следующие действия:

— Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

— Передвигаться на одну ячейку влево или вправо.

— Менять свое внутреннее состояние.

Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки («←” — влево, «→” — вправо, «точка” — нет перемещения) и новое состояние автомата qk.

Например, команда 1 «←” q2 обозначает «заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.

Предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

Т.о. можно дать формальное определение алгоритма по Тьюрингу. Машина Тьюринга — математический объект, и данное на ее основе определение алгоритма может использоваться для доказательства.

Примеры работы машины Тьюринга

На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.

Чтобы решить задачу, нам нужно:

-определить алфавит машины Тьюринга А,

— определить набор состояний Q,

— составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)

Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А=<1,0,a0>.

Определим возможные состояния:

1. q1 — автомат ищет правый конец слова (числа) на ленте

2. q2 — автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.

1 часть. q1 — автомат ищет правый конец слова (числа на ленте)

1)если в рабочей ячейке записано 0 — переместиться вправо

2)если в рабочей ячейке записано 1 — переместиться вправо

3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2

Составим таблицу переходов для q1 т.о.:

2 часть. q2 — автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.

1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп

2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд — записать в ячейку 0 и переместиться влево.

3) если в рабочей ячейке пробел, записать в нее 1 и стоп.

Добавим в нашу таблицу состояние q2:

Построенная таблица и есть программа для машины Тьюринга.

Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.

Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).

Требуется заменить все символы # и $ на нули. В момент запуска головка находится над любой буквой слова.

Вопросы: 1

1. Что такое универсальный исполнитель?

2. Опишите устройство и систему программирования машины Тьюринга.

3. Что такое состояние машины Тьюринга?

4. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?

5. В чем особенность состояний q0 и q1 машины Тьюринга?

6. По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?

7. Сформулируйте тезис Чёрча — Тьюринга.

Компьютерный практикум:

(Методические материалы И.Г. Семакина. Сетевой семинар «Преподавание профильного курса информатики»)

1. Дано целое число в троичной системе счисления; нужно увеличить его на единицу. Для реализации программы использовать учебную модель машины Тьюринга.

2. К данному троичному числу прибавить 2.

3. Прибавление единицы для целых чисел в пятеричной системе счисления

4. Составьте два варианта программы для машины Тьюринга, решающей следующую задачу: целое десятичное число нужно умножить на 10. Головка автомата расположена: а) левее числа на какой-то свободной ячейке; б) правее числа на какой-то свободной ячейке.

5. На ленте машины Тьюринга слева от головки автомата расположена группа подряд стоящих звездочек. Нужно стереть все звездочки и получить на ленте число, равное первоначальному количеству звездочек. Составить программу, реализовать ее на учебной модели машины Тьюринга. Протестировать программу.

Машина Тьюринга программа (К. Поляков)

Дополнительный материал:

1. Тренажер для изучения работы машины: программа (К. Поляков) (пароль к архиву kpolyakov.narod.ru)

4. Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машины Тьюринга и алгоритмы Маркова. Решение задач. М.: МГУ, 2006.

1. К.Ю. Поляков, Е.А. Еремин «Элементы теории алгоритмов». Журнал «Информатика» №1, 2012 г.

Оценка статьи:

Загрузка...

Машина тьюринга паскаль Ссылка на основную публикацию

Похожие публикации

• 
  Запись в текстовый файл паскаль

wpDiscuz

Adblock
detector