Описание тега turing-machines

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

Как формально описать этот алгоритм для машины Тьюринга?

Уоринг: Эту задачу дал мой профессор, которому 80 лет, и никто не понимает, чего он иногда хочет, я не ожидаю более менее стандартного подхода к этой проблеме, не только потому, что проблема трудная, но и потому, что мой профессор стар Школа экс-сум…
16 май '18 в 21:01
1 ответ

Алгоритмы машины Тьюринга

Я пытаюсь определить, как машина Тьюринга (состоящая только из 0 и 1, без пробелов) может распознавать последовательность из 8 1. Каждый алгоритм, который я обнаружил, имеет TM, ищущий неопределенное число 1 или 0, а не конкретное число. По сути, ес…
26 окт '17 в 18:39
1 ответ

Пересечение двух разрешимых по Тьюрингу языков разрешимо по Тьюрингу

Докажите, что пересечение двух языков, разрешимых по Тьюрингу, разрешимо по Тьюрингу. (Учитывая алгоритмы для выбора каждого языка, опишите алгоритм, чтобы определить, принадлежит ли строка к пересечению.) Я знаю, что язык является разрешимым по Тью…
05 дек '15 в 20:30
1 ответ

Построение недетерминированной машины Тьюринга

Нарисуйте схему двухдетерминированной недетерминированной машины Тьюринга M, которая решает язык L = {w∈Σ * | w = uu u ∈Σ *} Если бы я мог получить помощь в объяснении шагов, как построить NDTM (лингвистически), я бы мог нарисовать диаграмму, но я н…
09 янв '17 в 16:40
1 ответ

Когда машины Тьюринга имеют конечные состояния?

Это может быть глупый вопрос, но когда у машин Тьюринга есть конечные состояния? Я вижу некоторых с конечными состояниями, а некоторых нет, я сейчас немного растерялся.
23 янв '18 в 20:44
3 ответа

Полный словарь

Под "словарем" я подразумеваю массив пар ключ / значение с уникальными ключами. Если нет, то почему? Если достаточно долго, вы можете использовать ключ в качестве входных данных и значение в качестве выходных данных, и это может решить столько пробл…
12 май '11 в 04:11
1 ответ

Конечные автоматы, автоматы Pushdown и примеры машин Тьюринга

Я ищу хороший источник примеров конечных автоматов, автоматов раскрытия и задач машины Тьюринга (для решения вручную, вручную). Я искал вокруг, но не нашел ничего особенного, поэтому мне интересно, есть ли у кого-нибудь хорошие примеры. Заранее спас…
28 авг '12 в 17:30
1 ответ

Учитывая кодировку конкретной машины Тьюринга, можно ли решить, остановится ли она на конкретном входе?

Скажем, у меня есть универсальная машина Тьюринга, кодирующая конкретную машину Тьюринга T. Также скажите, что у меня есть кодировка конкретного ввода s. Вопрос о том, останавливается ли T на s, разрешим? Можно ли использовать симуляцию бега T на s,…
28 июл '17 в 01:55
4 ответа

Полнота по Тьюрингу

Таким образом, можно сказать, что язык является полным по Тьюрингу, если он удовлетворяет некоторым критериям, и он может делать все, что может сделать другой полный по Тьюрингу язык. Значит ли это, что я теоретически могу реализовать Google, исполь…
11 сен '10 в 01:10
1 ответ

Наличие некоторого файла XML/Json для компиляции в Graphiz / Finite State Automaton. Какие-либо предложения?

У меня есть задача, где мне нужно сделать несколько существующих снимков [которые показывают некоторые автоматы (DFA, NFA, машины Тьюринга)] и каким-то образом преобразовать их в формат, который позволяет мне использовать данные, чтобы представлять …
02 ноя '10 в 11:21
1 ответ

Реализуйте перечислитель, используя машину Тьюринга - избыточные отпечатки

По следующему алгоритму: мы реализуем перечислитель, используя машину Тьюринга, и предполагается, что перечислитель выводит язык, принятый машиной Тьюринга. Принятые слова из Σ* печатаются несколько раз (на каждой итерации ранее напечатанные слова б…
17 мар '18 в 17:15
1 ответ

Машины Тьюринга для уравнения с модулем

Мне нужно создать туристический автомат для Z =(Xi + Ki)mod 2 но я полностью потерян с точки зрения создания туристической машины по модулю 2. X и K - двоичные входы, где i - длина строки. Вход дан как таковой, где: XYK Y просто действует как раздел…
25 сен '17 в 11:01
1 ответ

Может ли язык принимать бесконечные числа

У меня есть вопрос, может ли язык принимать бесконечные числа Я должен уменьшить Лемпти до Линфа where Lempty ={e|L(Pe) is null} Linf={e|L(Pe) is infinite} так я могу определить программу P, как это " input n Run Pe on 1...n for n steps if Pe accept…
11 мар '13 в 00:33
3 ответа

В чем разница между ласточкиным хвостом и параллелизмом?

Я столкнулся с определением ласточкиного хвоста, о котором раньше не слышал, и первое, что пришло мне в голову, - это параллелизм. Однако я не смог найти ни одного поста, связанного с этими двумя понятиями. Я тоже читал это. Если я не ошибаюсь, "лас…
08 мар '16 в 09:19
1 ответ

Разрешается ли использование CFG с использованием нулевого языка?

Если у меня есть контекстно-свободная грамматика G такая, что язык G ноль, можно ли решать G? Я знаю, что ответ - да, но мне трудно доказать это. Моя первая мысль состоит в том, чтобы сказать, что есть только одно состояние, q1, которое является нач…
22 мар '11 в 05:33
0 ответов

Пошаговое выполнение функции для моделирования машины Тьюринга?

Просто случайный вопрос - есть ли способ запустить функцию Python шаг за шагом? Я хочу иметь возможность имитировать такие вещи, как ласточкин хвост - где для каждого ввода я могу запустить один шаг функции за раз, чтобы он выводил все операторы воз…
03 май '17 в 18:34
1 ответ

Почему мы должны использовать отрицание в Доказательстве остановки Тьюринга?

Например, допустим, у меня есть машина Тьюринга H, которая сообщает нам, остановится ли программа и ввод. Допустим, мы называем H на себя. Он должен дать ответ, поэтому, если он печатает "не останавливается", то не технически ли он останавливает печ…
01 фев '15 в 07:24
1 ответ

Машина Тьюринга, которая не принимает - как мы можем это знать?

Предположим, у меня есть TM M, который принимает язык L. Если я дам ему входное слово w и захочу узнать, принимает ли он его или нет, - могу ли я утверждать, не объясняя, что я делаю, если M НЕ принимает w? Я имею в виду - фраза "если М не принимает…
07 апр '18 в 11:25
2 ответа

Почему язык сценариев должен быть "намеренно неполным по Тьюрингу"?

Итак, я читал о Bitcoin Script в их официальной документации и нашел следующую строку: "Скрипт прост, основан на стеке и обрабатывается слева направо. Он специально не является полным по Тьюрингу, без циклов". Я пытался рассуждать трудно, но не мог …
03 фев '15 в 00:00
1 ответ

Универсальная машина Тьюринга U должна определить, останавливается ли M(x)

Итак, у нас есть универсальная машина Тьюринга U, которая должна определить, остановится ли машина Тьюринга M с входом x. Решение должно быть представлено в псевдокоде. Может ли кто-нибудь помочь мне немного, кто я должен решить это?
08 ноя '13 в 14:58