Форумы «Творчество»

ПОДСКАЗКА К КОНКУРСУ: Машина Тьюринга

задолбаешься переводить)))

Urlaban
все намного проще)))

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

ScorpionFish
напал на след

serg1254
Если это ответ то он не верный)

777РомА777
Отлично)

Мозг убил окончательно

Chelovek

html :))))

10 часов . и нихрена(

Начала
Тезис Чёрча-Тьюринга
Проблема останова
Машина Тьюринга
Расшифровка кода «Энигмы»
Создание одного из первых компьютеров
Основатель теории искусственного интеллекта
Тест Тьюринга
Преследование за гомосексуальность и смерть Тьюринга
Память об Алане Тьюринге
Литература

Тезис Чёрча-Тьюринга
Проблема останова
Машина Тьюринга
Расшифровка кода «Энигмы»
Создание одного из первых компьютеров
Основатель теории искусственного интеллекта
Тест Тьюринга
Преследование за гомосексуальность и смерть Тьюринга
Память об Алане Тьюринге
Литература

не видел знаков в принципе работы машины тьюринга только стрелка есть во всём основном ( + и -) ничего не встретил

НьютонМЕДВЕД
хватит копировать мои коментарии

David-1
)))

НьютонМЕДВЕД
что ))) ??? что сам искать и думать тяжело?

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

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

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

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

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

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

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



или


Умножим с помощью МТ 3 на 2 в единичной системе. В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).

Начало. Находимся в состоянии q0, ввели в машину данные: *111x11=*, головка машины располагается на первом символе *.

1-й шаг. Смотрим по таблице правил что будет делать машина, находясь в состоянии q0 и над символом "*". Это правило из 1-го столбца 5-й строки - q0*→q0*R. Это значит, что мы переходим в состояние q0 (т.е. не меняем его), символ станет "*" (т.е. не изменится) и смещаемся по введённому нами тексту "*111x11=*" вправо на одну позицию (R), т.е. на 1-й символ 1. В свою очередь, состояние q01 (1-й столбец 1-я строка) обрабатывается правилом q01→q01R. Т.е. снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ "х". И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.

Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву "а", и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на "а" и дописывания такого же количества единиц в конце строки (слева от крайнего правого "*"). Затем меняем все "а" до знака умножения "х" обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой "а" и снова переносим единицы. Когда до знака "=" не окажется единиц - значит умножение завершено.

Chelovek


David-1
НЕТ не верно

777РомА777

Гамовер


Спасибо)) Я уже это читал)))