В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных...

Тьюринга Вычислимая функция Разрешимое множество Алгоритмически неразрешимая задача Трансвычислительная задача Мальцев А. И. . Алгоритмы и рекурсивные функции...

которая называется тезис Чёрча: Числовая функция тогда и только тогда алгоритмически исчисляется, когда она частично рекурсивна. Доказательство того, что...

который предсказывает F. Для многих других задач[каких?] можно доказать их алгоритмическую неразрешимость, попытавшись свести их к проблеме остановки...

модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности...

формальную запись этого же алгоритма. Задача распознавания самоприменимости является алгоритмически неразрешимой и сводится к тому, чтобы найти алгоритм...

вычислений и вычислимости, и доказательство того, что существуют алгоритмически неразрешимые задачи. Введено понятие языка программирования, то есть средства...

выводимо, что снова невозможно. В стандартной интерпретации гёделева неразрешимая формула A означает «не существует вывода формулы A», то есть утверждает...

Тьюринг показал наличие алгоритмически неразрешимых задач, в частности доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. Существование...

алгоритма с наименьшим возможным размером на выходе является алгоритмически неразрешимой задачей. Если в архив упаковывается много файлов, имеющих похожую...

произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют...