2024
2023
2022
2021
2020
2019
2018
2017
Задание
Для всех задач на написание программы для машины Тьюринга обязательно уметь объяснять про каждое состояние, зачем оно нужно и за какую задачу оно отвечает.
(0.5 балла) Алфавит состоит из букв и знаков < и >. На ленте написано слово в угловых скобках <>. Изначально машина стоит на знаке <. Написать после знака > то же слово задом наперёд.
Пример входа: <abcd>
Для него выход: <abcd>dcba
(0.5 балла) Алфавит состоит из букв ACGT и знаков < и >. На ленте написана нуклеотидная последовательность в угловых скобках <>. Изначально машина стоит на знаке <. Написать после знака > комплементарную последовательность.
Пример входа: <aaagatc>
Для него выход: <aaagatc>gatcttt
(0.5 балла) Алфавит состоит из цифр 0, 1, и знаков + и =. На ленте написано выражение вида = цифра + цифра. Изначально машина стоит на знаке =. Написать перед знаком равенства сумму одноциферных чисел в двоичной системе исчисления.
Пример входа: =1+0
Для него выход: 1=1+0
(0.5 балла) Алфавит состоит из цифр 0, 1, и знаков + и =. На ленте написано выражение вида = цифра цифра + цифра. Изначально машина стоит на знаке =. Написать перед знаком равенства сумму чисел в двоичной системе исчисления.
Пример входа: =11+1
Для него выход: 100=10+1
(1 балл) Алфавит состоит из цифр 0, 1, и знаков ;, + и =. На ленте написано выражение вида = число + число ;. Изначально машина стоит на знаке =. Написать перед знаком равенства сумму чисел в двоичной системе исчисления.
Пример входа: =111+101
Для него выход: 1100=111+101
(0.5 балла) Алфавит состоит из цифры 1 и знаков ;, + и =. На ленте написано выражение вида число + число ;. Изначально машина стоит на первой цифре числа. Заменить выражение на сумму двух чисел в унарной системе исчисления.
Пример входа: 111+11
Для него выход: 11111
(0.5 балла) Алфавит состоит из букв a и b и знаков '<' и '>'. На ленте написано выражение вида < слово >. Изначально машина стоит на первой букве слова. Отсортировать буквы в слове (т.е. поставить все буквы a слева, а все буквы b справа).
Пример входа: <babbaaabb>
Для него выход: <aaaabbbbb>
(1 балл) Напишите (на любом ЯП) интерпретатор машины Тьюринга, который принимает на вход описание машины (состяния, переходы, начальное состояние) в одном файле, и входные данные (содержимое ленты, начальное положение) в другом файле, и выводит на экран последовательность состояний машины и ленты в процессе исполнения.
(2 балла) Напишите (на любом ЯП) графический интерпретатор машины Тьюринга, который изображает состояние машины и ленты на каждом шагу и позволяет как идти пошагово, так и запустить машину двигаться с некоторой стандартной скоростью.