Вопросы по теме 'turing-machines'
Как иерархия Хомского и машины Тьюринга должны влиять на дизайн языка?
В настоящее время я готовлюсь к тесту по дискретной математике, в котором мы изучаем иерархию Хомского и тип автоматов, распознающих каждый уровень иерархии. Меня учат, что большинство компьютерных языков попадают в «уровни 2 и 1» иерархии, но не...
2063 просмотров
schedule
14.12.2022
Каковы полезные пределы линейных ограниченных автоматов по сравнению с машинами Тьюринга?
Есть языки, с которыми машина Тьюринга может справиться, но с которыми не может справиться LBA, но есть ли какие-нибудь полезные практические проблемы, которые не может решить LBA, но могут решить TM?
LBA — это просто машина Тьюринга с ограниченной...
2695 просмотров
schedule
12.03.2022
Почему это недействительная машина Тьюринга?
Во время проверки экзамена у меня возникли проблемы с ответом на следующий вопрос из книги «Введение в теорию вычислений» Сипсера. К сожалению, в книге нет ответа на этот вопрос.
Объясните, почему следующее не является законной машиной Тьюринга....
6024 просмотров
schedule
20.05.2024
Разработайте автоматы Push Down для подсчета количества символов
Алфавит: a, b, c Я пытаюсь определить КПК, который принимает
a^n b^m c^p : n + p = 2k for some integer k, m = k, and n, m, p, k >= 0
Я думаю, что допустимы следующие строки: #abc#; #aabbcc#; #aaabbbccc#; #аббкк#; #aaabbc# и т.д....
2983 просмотров
schedule
10.05.2022
Можно ли построить машину Тьюринга, используя только два ленточных символа?
Машина Тьюринга M, содержащая любое количество ленточных символов, может быть смоделирована одним M', содержащим всего три ленточных символа: {0, 1, B} (B = Пусто).
Можно ли смоделировать М с помощью М", который имеет только два символа ленты,...
2827 просмотров
schedule
15.01.2023
Как определить, является ли язык рекурсивным или рекурсивно перечислимым?
Я должен определить, является ли язык (например, L={a^n b^m c^s | 0‹=n‹=m‹=s}) регулярным, контекстно-свободным, рекурсивным, рекурсивно перечислимым или ни одним из них.
Я знаю, как определить, является ли язык регулярным (найдите DFA или...
16181 просмотров
schedule
27.11.2022
Минимизация конечного автомата
Я пытаюсь минимизировать этот DFA: http://img145.imageshack.us/img145/3006/dfac.png
Вот мой свернутый DFA: http://img195.imageshack.us/img195/4131/mdfa.png
Я прав? Спасибо
P.S. Это домашнее задание. Нам разрешено обсуждать домашнее...
391 просмотров
schedule
12.06.2023
Как алгоритмы и структуры данных связаны с машинами Тьюринга?
Моя копия Дизайн и анализ компьютерных алгоритмов прибыл сегодня. В первой главе автор представил машины Тьюринга. У меня есть еще два учебника по алгоритмам: Введение в алгоритмы и Руководство по разработке алгоритмов , но ни один из них...
2034 просмотров
schedule
25.03.2022
Реализация машины Тьюринга на C
Я изучаю машины Тьюринга для своего курса теории формальных языков, профессор рекомендовал запустить следующий алгоритм , чтобы подробно увидеть логику «TM», но не работает, при попытке компиляции выдает следующую ошибку.
C:\Documents and...
10101 просмотров
schedule
17.06.2023
Машина Тьюринга, которая находит четную или нечетную длину
У меня есть вопрос, на котором я застрял:
Опишите формально (т. е. с помощью функции перехода) машину Тьюринга, которая решает, имеет ли входное слово a^n четную или нечетную длину.
Кто-нибудь, пожалуйста, сможет просветить меня о том, что меня...
9336 просмотров
schedule
21.04.2023
натуральные числа и разница между узнаваемыми и разрешимыми?
Я нашел следующее объяснение от Math exchange
Язык является распознаваемым тогда и только тогда, когда существует машина Тьюринга, которая остановится и примет только строки на этом языке, а для строк не на этом языке ТМ либо отклонит, либо не...
292 просмотров
schedule
03.07.2022
Машины Тьюринга и эквивалентность лямбда-исчисления
Мне интересно, может ли кто-нибудь объяснить мне в общих чертах некоторые доказательства эквивалентности лямбда-исчисления и машин Тьюринга, а также общий метод доказательства. Максимально простыми словами.
1090 просмотров
schedule
28.08.2023
Не могу понять решение (машина Тьюринга и редукция)
Нажмите здесь, чтобы увидеть мою проблему
Hi.
Что касается этого вопроса, я просто не могу понять его решение.
Мы знаем дополнение Atm = { <M,W> : M является TM и M не принимает W} и Rtm, как описано на фото = { <M,W> : M...
211 просмотров
schedule
13.04.2023
Машина Тьюринга при следующих входных данных: 1010
Я готовлюсь к экзаменам и понятия не имею, как составить таблицу состояний машины Тьюринга, учитывая следующие входные данные 111101 (состояние, ввод/чтение, запись, перемещение, следующее состояние). Любая идея, где я могу получить упрощенные...
109 просмотров
schedule
06.05.2022
Существуют ли какие-либо рекурсивно перечисляемые проблемы, которые не являются RE-сложными?
Класс вычислимости, который я беру, объясняет несколько языков, которые находятся в RE - REC (рекурсивно перечисляемые, но не рекурсивные, т.е. решаемые безостановочной машиной Тьюринга). Сначала показано, как один из них (L_d, язык машин Тьюринга,...
484 просмотров
schedule
25.02.2022
Что такое функция уменьшения отображения
Это (я думаю) простая задача из теории сложности.
#Consider the language E over the binary alphabet
#consisting of strings representing even non-negative
#integers (with leading zeros allowed).
#I.e. E = {x | x[-1] == '0'}.
#
#Reduce E to the...
202 просмотров
schedule
22.12.2022
Как узнать, является ли машина Тьюринга решающим фактором?
Есть ли простой способ приблизиться к этому? Могу ли я определить, является ли он решающим, посмотрев на схему машины Тьюринга?
5526 просмотров
schedule
05.08.2022
что означают регулярные, распознаваемые по Тьюрингу и распознаваемые по Тьюрингу?
Я знаю, что этот вопрос задавался ранее, но, честно говоря, я не совсем понимаю его.
В настоящее время я изучаю теорию вычислений и подхожу к термину «Докажите, что язык разрешимый, узнаваемый или регулярный».
Проще говоря, что они на самом деле...
2228 просмотров
schedule
02.12.2022
Почему лямбда-переходов нет в машине Тьюринга?
Лямбда-переход не определен в машинах Тьюринга? В чем причина этого? Кто-нибудь, пожалуйста, объясните мне.
Заранее спасибо.
1118 просмотров
schedule
27.07.2023
Как приступить к созданию машин Тьюринга для конкретных языков?
до сих пор я столкнулся с двумя типами языков. Языки, в которых существует строгий формат, например
L = {a^n b^n c^n | n >= 1}
Этот язык строг, например, a всегда будет стоять перед b и т. д.
другой тип, с которым я столкнулся, - это языки,...
167 просмотров
schedule
22.08.2022
