Предоставляется ли == Разрешаемо?

Question

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

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

Answer 1

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

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

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

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