Публикации по теме 'halting-problem'
Доказательство того, что проблема остановки неразрешима (для программистов-непрофессионалов)
Есть задачи, которые вычислительно невозможны. Они относятся к классу неразрешимых задач. Для неразрешимой задачи не существует алгоритма, который решает задачу на каждом входе независимо от времени работы алгоритма. Вы запускаете полиномиальное время, экспоненциальное время; нет алгоритма, который собирался бы решить это на каждом входе.
В 1936 году великий Алан Тьюринг доказал, что проблема остановки неразрешима. И мы увидим идею этого результата сейчас. Эта статья Тьюринга в..
Вопросы по теме 'halting-problem'
Почему нельзя исключить бесконечный цикл?
Правило «как если бы» подпадает под следующие правила:
Наименьшие требования к соответствующей реализации:
Доступ к изменчивым объектам оценивается строго по правилам абстрактной машины.
При завершении программы все данные, записанные в...
98 просмотров
schedule
28.11.2021
Немного другая версия проблемы остановки
У меня возник вопрос, и я хотел бы получить небольшое руководство по его решению.
Мне нужно доказать, что следующая проблема неразрешима: Вход - программа Проблема - больше ли количество возможных входов, для которых программа останавливается...
75 просмотров
schedule
14.11.2021
Есть ли достаточно хорошее решение проблемы остановки?
Известно, что проблема остановки не может иметь определенного решения, которое: а) возвращает true ‹==> программа действительно останавливается, и б) обрабатывает любой ввод, но мне было интересно, есть ли достаточно хорошие решения проблемы, те,...
3530 просмотров
schedule
07.03.2022
Объяснение проблемы остановки машины Тьюринга
Я ищу простое объяснение проблемы остановки машин Тьюринга. Я знаю основы того, как работают TM, как они перечисляют вещи, конфигурации машин и т. Д., Но я плохо разбираюсь в проблеме остановки.
Может ли кто-нибудь дать хорошее объяснение этой темы?
385 просмотров
schedule
30.03.2022
Все ли регулярные выражения останавливаются?
Есть ли какое-нибудь регулярное выражение, которое для некоторой входной строки будет вечно искать совпадение?
1603 просмотров
schedule
16.05.2022
Решает ли Glorious Glasgow Haskell Compilation System проблему остановки наполовину?
заголовок длинный, потому что SO не разрешил. Решает ли GHC проблему остановки наполовину? почему-то
Конечно, не собственно проблема остановки, а подзадача конечной памяти.
Я игрался с метапрограммированием а-ля набрав техническое интервью и...
27 просмотров
schedule
30.07.2022
В чем именно заключается проблема остановки?
Когда люди спрашивают о проблеме остановки, связанной с программированием, люди отвечают: «Если вы просто добавите один цикл, у вас есть программа остановки и, следовательно, вы не сможете автоматизировать задачу ».
Имеет смысл. Если ваша...
22857 просмотров
schedule
21.07.2023
Автоматическое и детерминированное тестирование функции на ассоциативность, коммутативность и т. д.
Можно ли построить функцию более высокого порядка isAssociative , которая принимает другую функцию с двумя аргументами и определяет, является ли эта функция ассоциативной?
Аналогичный вопрос, но и для других свойств, таких как коммутативность....
457 просмотров
schedule
14.10.2022
Является ли mfix для Maybe невозможным быть нетривиально тотальным?
Поскольку Nothing >>= f = Nothing для каждого f , для mfix подходит следующее тривиальное определение:
mfix _ = Nothing
Но это не имеет практического применения, поэтому мы имеем следующее неполное определение:
mfix f = let a =...
175 просмотров
schedule
14.02.2023
