Определение вычислимого?

Question

Мне интересно, что было бы «кратким» определением вычислимого?Я спрашиваю, потому что я запутался в том, что вычислимо или нет.

Является ли что-то вычислимым только в том случае, если оно останавливается?Например,

function foo(){
 while(true);
}

не вычислимо просто потому, что оно никогда не останавливается?Или я путаю определение computable с проблемой остановки?

Спасибо

Answer 1

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

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

Два интересных результата изучения вычислимости:

• Некоторые классы компьютеров более ограничены, чем другие, в отношении того, что на них вычисляется, но даже некоторые очень простые модели (например, машины Тьюринга) могут вычислять все, что мы знаем, как вычислять.
• Некоторые проблемы могут быть доказаны как неисчисляемые или неразрешимые. Проблема остановки - одна из таких проблем.

Answer 2

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

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