22
ответа

Когда теоретическая информатика полезна?

В классе мы узнали о проблеме остановки, Машинах Тьюринга, сокращениях, и т.д. Много одноклассников говорит, что это все абстрактные и бесполезные понятия, и нет никакого основного назначения в знании их (...
вопрос задан: 29 December 2016 21:39
21
ответ

Какова точно проблема остановки?

Каждый раз, когда люди спрашивают о проблеме остановки, поскольку она принадлежит программированию, люди отвечают, "Если Вы просто добавляете один цикл, у Вас есть останавливающаяся программа, и поэтому Вы не можете автоматизировать задачу", Дел
вопрос задан: 23 May 2017 02:10
11
ответов

Когда Вы натолкнулись на проблему остановки в поле? [закрытый]

Когда Вы когда-либо лично наталкивались на проблему остановки в поле? Это может быть, когда коллега / босс предложил решение, которое нарушит фундаментальные пределы вычисления, или когда...
вопрос задан: 6 November 2018 15:38
8
ответов

Все регулярные выражения останавливаются?

Есть ли какое-либо регулярное выражение, которое, для некоторой входной строки, будет искать соответствие навсегда?
вопрос задан: 6 August 2009 20:28
7
ответов

Практические нетурингово-полные языки?

Почти все используемые языки программирования являются Turing Complete, и хотя это позволяет использовать язык для представления любого вычислимого алгоритма, он также имеет свой собственный набор проблем. Видя, как все ...
вопрос задан: 12 May 2014 17:00
7
ответов

Обнаружение бесконечного цикла в brainfuck программе

Я записал простой brainfuck интерпретатор на языке сценария MATLAB. Это питается случайные bf программы для выполнения (как часть проекта генетического алгоритма). Проблема, с которой я сталкиваюсь, программа складывается...
вопрос задан: 24 December 2008 11:41
6
ответов

Существует ли “достаточно хорошее” решение для проблемы остановки?

Известно, что проблема остановки не может иметь определенного решения, то, которое a) возвращает true <==>, программа действительно останавливается и b) обрабатывает любой вход, но я задавался вопросом, хороши ли там...
вопрос задан: 18 March 2010 00:00
3
ответа

Остановка на неполных по Тьюрингу языках

Проблема остановки не может быть решена для полных по Тьюрингу языков, и она может быть решена тривиально для некоторых языков неTC как regexes, где она всегда останавливается. Я задавался вопросом, существует ли кто-либо...
вопрос задан: 21 July 2016 16:29
0
ответов

Доказательство того, что проблема остановки является NP-сложной?

В этом ответе на вопрос об определениях NP, NP-hard и NP -complete, Джейсон утверждает, что проблема остановки является классической NP-сложной проблемой. Это проблема, которая дает ...
вопрос задан: 18 December 2018 06:52
0
ответов

Как работает это доказательство того, что проблема остановки неразрешима?

Я просматриваю доказательство проблемы остановки во введении к теории вычислений, написанное Сипсером, и меня больше всего беспокоит приведенное ниже доказательство: Если TM M не знает, когда он зацикливается (он не может принять ...
вопрос задан: 9 November 2018 14:58
0
ответов

«Поиск всего кода в заданном двоичном файле эквивалентен проблеме остановки». В самом деле?

Я только что прочитал получивший большое количество голосов вопрос относительно эмуляторов и утверждение. Было доказано, что поиск всего кода в заданном двоичном файле эквивалентен проблеме остановки. На самом деле ...
вопрос задан: 23 May 2017 10:24
0
ответов

Бесконечные циклы в Java

Посмотрите на следующий бесконечный цикл while в Java. Это вызывает ошибку времени компиляции для оператора под ним. while (истина) {System.out.println ("внутри в то время как"); } System.out.println ("while ...
вопрос задан: 11 October 2014 17:50
0
ответов

Автоматическое и детерминированное тестирование функции на ассоциативность, коммутативность и т.д.

Можно ли построить функцию более высокого порядка isAssociative, которая принимает другую функцию двух аргументов и определяет, является ли эта функция ассоциативной? Аналогичный вопрос, но для других ...
вопрос задан: 28 December 2011 06:20