История изменений

Потому что очень многие проблемы в CS часто можно легко свести к проблеме останова. Соответственно, если программа, их описывающая, завершается, то у проблемы есть решение. Но для этого, конечно же, используются языки без Тьюринговой полноты.

Слишком много намешано и получилась каша.

Компьютеры могут практически использоваться для поиска контрпримеров к математическим гипотезам (например, поиск нулей дзета-функции для опровержения гипотезы Римана). Если остановился (то есть нашёл контрпример) - то гипотеза неверна.

Для проблем из CS обычно известно что решение есть (то есть программа поиска решения когда-то остановится и значит это не проблема останова), но из-за комбинаторного взрыва искать его тупым перебором слишком долго.

Для тех проблем из CS для которых известно что общего решения нет (то есть, проблема сводится к проблеме останова, которая не может быть решена в общем случае. Например, парсинг исходников C++), применяют эвристики. Ограничивают глубину рекурсии или время работы программы и вываливаются по ошибке по достижении этого предела.

Языки без Тьюринговой полноты применяются в тех случаях, когда по какой-то причине требуется гарантия останова.

Ну и слова «проблема останова» можно понять двумя способами:

1. Проблема остановки конкретной программы. Решаемость этой проблемы зависит от конкретной программы. (Опровержение математических гипотез находится здесь)

2. Проблема останова в теории алгоритмов: создать алгоритм для определения остановит-ли работу алгоритм поданный на вход. Эта проблема неразрешима на машине Тьюринга. (Парсинг С++ находится здесь)

Потому что очень многие проблемы в CS часто можно легко свести к проблеме останова. Соответственно, если программа, их описывающая, завершается, то у проблемы есть решение. Но для этого, конечно же, используются языки без Тьюринговой полноты.

Слишком много намешано и получилась каша.

Компьютеры могут практически использоваться для поиска контрпримеров к математическим гипотезам (например, поиск нулей дзета-функции для опровержения гипотезы Римана). Если остановился (то есть нашёл контрпример) - то гипотеза неверна.

Для проблем из CS обычно известно что решение есть (то есть программа поиска решения когда-то остановится и значит это не проблема останова), но из-за комбинаторного взрыва искать его тупым перебором слишком долго.

Для тех проблем из CS для которых известно что общего решения нет (то есть, проблема сводится к проблеме останова, которая не может быть решена в общем случае. Например, парсинг исходников C++), применяют эвристики. Ограничивают глубину рекурсии или время работы программы и вываливаются по ошибке по достижении этого предела.

Языки без Тьюринговой полноты применяются в тех случаях, когда по какой-то причине требуется гарантия останова.

Ну и слова «проблема останова» можно понять двумя способами:

1. Проблема остановки конкретной программы. Решаемость этой проблемы зависит от конкретной программы.

2. Проблема останова в теории алгоритмов: создать алгоритм для определения остановит-ли работу алгоритм поданный на вход. Эта проблема неразрешима на машине Тьюринга.

Потому что очень многие проблемы в CS часто можно легко свести к проблеме останова. Соответственно, если программа, их описывающая, завершается, то у проблемы есть решение. Но для этого, конечно же, используются языки без Тьюринговой полноты.

Слишком много намешано и получилась каша.

Компьютеры могут практически использоваться для поиска контрпримеров к математическим гипотезам (например, поиск нулей дзета-функции для опровержения гипотезы Римана). Если остановился (то есть нашёл контрпример) - то гипотеза неверна.

Для проблем из CS обычно известно что решение есть (то есть программа поиска решения когда-то остановится и значит это не проблема останова), но из-за комбинаторного взрыва искать его тупым перебором слишком долго.

Для тех проблем из CS для которых известно что общего решения нет (то есть, проблема сводится к проблеме останова, которая не может быть решена в общем случае. Например, парсинг исходников C++), применяют эвристики. Ограничивают глубину рекурсии или время работы программы и вываливаются по ошибке по достижении этого предела.

Языки без Тьюринговой полноты применяются в тех случаях, когда по какой-то причине требуется гарантия останова.

Ну и слова «проблема остановки» можно понять двумя способами:

1. Проблема остановки конкретной программы. Решаемость этой проблемы зависит от конкретной программы.

2. Проблема остановки в теории алгоритмов: создать алгоритм для определения остановит-ли работу алгоритм поданный на вход. Эта проблема неразрешима на машине Тьюринга.

Потому что очень многие проблемы в CS часто можно легко свести к проблеме останова. Соответственно, если программа, их описывающая, завершается, то у проблемы есть решение. Но для этого, конечно же, используются языки без Тьюринговой полноты.

Слишком много намешано и получилась каша.

Компьютеры могут практически использоваться для поиска контрпримеров к математическим гипотезам (например, поиск нулей дзета-функции для опровержения гипотезы Римана). Если остановился (то есть нашёл контрпример) - то гипотеза неверна.

Для проблем из CS обычно известно что решение есть (то есть программа поиска решения когда-то остановится и значит это не проблема останова), но из-за комбинаторного взрыва искать его тупым перебором слишком долго.

Для тех проблем из CS для которых известно что общего решения нет (то есть, проблема сводится к проблеме останове, которая не может быть решена в общем случае. Например, парсинг исходников C++), применяют эвристики. Ограничивают глубину рекурсии или время работы программы и вываливаются по ошибке по достижении этого предела.

Языки без Тьюринговой полноты применяются в тех случаях, когда по какой-то причине требуется гарантия останова.

Ну и слова «проблема остановки» можно понять двумя способами:

1. Проблема остановки конкретной программы. Решаемость этой проблемы зависит от конкретной программы.

2. Проблема остановки в теории алгоритмов: создать алгоритм для определения остановит-ли работу алгоритм поданный на вход. Эта проблема неразрешима на машине Тьюринга.

Потому что очень многие проблемы в CS часто можно легко свести к проблеме останова. Соответственно, если программа, их описывающая, завершается, то у проблемы есть решение. Но для этого, конечно же, используются языки без Тьюринговой полноты.

Слишком много намешано и получилась каша.

Компьютеры могут практически использоваться для поиска контрпримеров к математическим гипотезам (например, поиск нулей дзета-функции для опровержения гипотезы Римана). Если остановился (то есть нашёл контрпример) - то гипотеза неверна.

Для проблем из CS обычно известно что решение есть (то есть программа поиска решения когда-то остановится и значит это не проблема останова), но из-за комбинаторного взрыва искать его тупым перебором слишком долго.

Для тех проблем из CS для которых известно что общего решения нет (то есть, проблема сводится к проблеме останове, которая не может быть решена в общем случае. Например, парсинг исходников C++), применяют эвристики. Ограничивают глубину рекурсии или время работы программы и вываливаются по ошибке по достижении этого предела.

Языки без Тьюринговой полноты применяются в тех случаях, когда по какой-то причине требуется гарантия останова.