Вопрос

В теории вычислений термины доказуемые и решаемые взаимозаменяемые? Они имеют в виду то же самое?

Например, вы часто видите вопрос, является ли что -то доказуемое, называемое проблемой принятия решения (Das entscheidungsproblem).

Это было полезно?

Решение

Они разные. На самом деле они относятся к совершенно разным областям.

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

Доказуемое означает, что математическое утверждение может быть доказано, в общем, математическим доказательством.

На самом деле, вы не можете сравнить «решающе» и «доказуемые», поскольку эти атрибуты относятся к совершенно разным вещам.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top