Читать курсовую работу online по теме Многоголовочная машина Тьюринга. Раздел Информационное обеспечение, программирование, 33,. Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Зайцев В.Н. Резервы Обучения Чтению. Но следует отметить, что данная имитация неполная, так. Машина Тьюринга Курсовая Работа' title='Машина Тьюринга Курсовая Работа' />НОУ ИНТУИТ. Это позволяло нам игнорировать детали. Но в некоторых случаях этого недостаточно. Пусть, например, мы. Это. обычно делается так. Мы показываем, что проблема остановки сводится к этой задаче. Машина Поста, Тьюринга и алгоритмы Маркова. Для этого мы моделируем работу. При этом. нам важно, чтобы определение алгоритма было как можно проще. Таким образом, наш план таков. Мы опишем довольно просто. Тьюринга, затем объявим, что всякая вычислимая функция может быть вычислена на. Тьюринга. можно свести к вопросу о равенстве слов в полугруппе. Другая причина, по которой важны простые вычислительные модели. Тьюринга, адресные. Но этот вопрос выходит за рамки классической теории. Машины Тьюринга определение. Машина Тьюринга имеет бесконечную в обе стороны ленту. В каждой ячейке может быть. Один из символов алфавита выделен и называется. Машина Тьюринга Курсовая Работа' title='Машина Тьюринга Курсовая Работа' />В каждый момент головка находится в одной из ячеек. При этом также меняется. Еще надо договориться, с чего мы начинаем. Таким образом, чтобы задать машину Тьюринга, надо указать. Таблица переходов устроена следующим образом для каждой пары. Здесь сдвиг одно из чисел 1 влево, 0 на месте и 1 направо. Таким образом, таблица. S x A S x A x. В каждый момент имеется некоторая конфигурация, складывающаяся из. Z A, текущей позиции. S. Преобразование конфигурации в следующую. При этом, если новое состояние является одним из. Остается. договориться, как мы подаем информацию на вход машины и что. Будем считать, что алфавит. Входом и выходом машины будут конечные последовательности нулей и единиц двоичные слова. Если машина останавливается. Таким образом, любая машина Тьюринга задает некоторую частичную. Все такие функции естественно. Тьюринга. Машины Тьюринга обсуждение. Разумеется, наше определение содержит много конкретных деталей. Например, лента может быть. Можно придать машине две. Можно считать, что машина может либо написать новый. Можно. ограничить алфавит, считая, скажем, что в нем должно быть. Можно потребовать, чтобы в конце на ленте. Все перечисленные и многие другие изменения не меняют. Тьюринга функций. Конечно, есть и. небезобидные изменения. Например, если запретить машине. Как понять, какие изменения безобидны, а какие нет Видимо. Тьюринга, хотя бы небольшой. После этого уже. можно представлять себе возможности машины, не выписывая. В качестве примера опишем машину, которая удваивает входное слово изготавливает слово. XX. если на входе было слово. X. Если машина видит пробел входное слово пусто, она. Если нет, она запоминает текущий символ и ставит. Затем она движется. Имея некоторый опыт, можно за всеми этими фразами видеть. Тьюринга. Например, слова. Ясно и то, как ошибку. Пусть есть машина с большим алфавитом из N символов. Размер блока число k будет фиксирован так, чтобы внутри. Исходные символы 0, 1 и пустой. Для начала надо раздвинуть буквы входного слова на. Ясно, что в этом. После этого уже можно. Наконец, надо сжать результат обратно. Утверждение о том, что всякая вычислимая функция вычислима на. Тьюринга, называют тезисом Тьюринга. Конечно, его смысл зависит от того, что понимать под словами. Если понимать их в. Можно лишь говорить, что многовековая практика. Евклида до Кнута не встретилась с примером. Тьюринга и т. п. Впрочем, еще один не слишком убедительный. Но если понимать слово. Конечно, такое доказательство по необходимости. Впрочем, такого рода доказательства сродни. В заключение обсуждения приведем обещанный выше аргумент в. Тьюринга. Пусть есть функция, которую человек умеет вычислять. Будем считать, что он пишет на. Помимо текущего листа, есть стопка. У человека есть карандаш и ластик. Поскольку очень. мелкие буквы не видны, число отчетливо различимых. Человек тоже имеет конечную. При этом можно составить некоторую таблицу, в которой. Теперь уже видно, что действия человека как раз. Тьюринга с большим но конечным алфавитом и большим но конечным числом внутренних состояний.