МТ

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

Привет, Шурик и все товарищи по несчастью!

Вам надо:

1. Перечитать лекции № 6-7. Внимательно слушать лекции №9-11.
2. Посетить семинары по МТ и ДТ в своей и в других (!) группах.
3. Прочитать преамбулу к лаб. раб. №5, разобрать и погонять в пошаговом режиме примеры к ней. (Выдадим 26 сентября). После разбора примеров попытаться решить какую-нибудь простую задачку самостоятельно.
4. Поискать в списке литературы и почитать, что доступно.
5. Поискать в интернете и на диске CD-хрестоматии программы эмуляции МТ и примеры(тесты) к ним. Диск скоро появится ( !?! ) или найдите прошлогодний (на 3-х CD ROM).
6. Нанять недорогого репетитора (студента 1 курса 8 ф-та). Многие студенты нашего факультета легко справляются с задачами по МТ (25-30%).
7. Набрать группу желающих и заказать через кафедру краткий курс допзанятий на тему "Решение задач по МТ, ДТ и НАМ" (3 раза по 4 часа). При группе 15 чел. это будет стоить недорого.
8. Пытаться свою задачу делать самостоятельно, сначала словесно с иллюстрациями на бумаге расписать алгоритм аналогично примеру из лекции, потом составить таблицу в символических обозначениях и оттранслировать её в коды МТ как на лекции №8. Согласовать идею решения с преподавателем, убедиться, что задача понята правильно.
9. Задачи по МТ можно найти также в учебниках и задачниках по теории алгоритмов и дискретной математике, но обычно их немного, решениями и пошаговым разбором не балуют. Но Вы можете запутаться в обозначениях и в терминологии и зря потратить время.
10. Написать свой эмулятор МТ на Паскале, Си, Бейсике, Excel и т.д.(курсовая работа на ВМК).
11. Возможно, что Вам просто потребуется дополнительное время и усилия и Вы справитесь с МТ без посторонней помощи.
12. Дождитесь, наконец, пока другие решат свои задачи, и разберите их решения.

Шеннон, Маккарти. Часть 2. Машины Тьюринга
Эббинхаус, Якобс, Ман, Хермес. Машины Тьюринга и рекурсивные функции

Такие подойдут?



Валентин Евгеньевич, а у вас есть список литературы для первого курса в электронном виде? Если есть, не могли бы Вы мне его прислать?

Отдельную тему для тагого вопроса я создавать не решился и по этому задаю этот вопрос тут:

В позиционной системе счисления одна палочка равна нулю или еденице???? (задача с переводом числа в позиционную СС)

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

Интерпретаторы МТ пишутся на каждом курсе по мнугу штук

Вы бы лутше бы на вопрос ответили)

Тогда поподробнее: какая позиционная система??
Из какой перевод?

>В позиционной системе счисления одна палочка равна нулю или еденице???? (задача с переводом числа в позиционную СС)

Какая именно позиционная СС? Римская СС тоже позиционной бывает...

Из того, что вы имеете ввиду есть две: натуральная (одна палочка - единица) и кардинальная (одна палочка - ноль).

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

Кстати в слове "еденица" третья буква - "и" )

>Кстати , мной написан весьма неплохой интерпретатор МТ для виндовс

Я помницца интерпретатор написал в 46 строк (питон). У кого короче!!! ))))))

В натуральной с/c палочка единица, а в кардинальной -- нуль. Эти системы, также как и римская, непозиционные, во всяком случае не с полиномиальной интерпретацией.

НАМ на Прологе у моей аспирантки был ещё короче!

В прынцыпе кардинальная и натуральная несильно-то отличаются:
шаг влево-ставим палку-шаг влево. ВСЁ далее алгоритм для натуральной СС - вот и вся разница.

???
Мне казалось, "ставим палку-шаг вправо".



-----

студент, 4 курс

На самом деле это вопрос далеко не очевидный. Если положить основание системы счисления p=1, то 1111 в натуральной системе можно вычислить по полиномиальной формуле 4=1*1^3+1*1^2+1*1^1+1*1^0. Если придерживаться определения, что позиционные системы - это системы, в которых функция интерпретации полиномиальна, то получается, что натуральная система вполне этому определению удовлетворяет.



----
Сошников Д.В.
доцент кафедры Вычислительной математики и программирования МАИ
[www.mailabs.ru]

>???
>Мне казалось, "ставим палку-шаг вправо".

Пардон, очепятка...

Про позиционно-непозиционные системы счисления смотрите в лекциях!

Конечно спасибо , но я уже все работы по этому заданию завершил))