1.5.4 Вычислимые функции, полнота формализации понятия вычислимости, универсальная вычислимая функция
Видеоурок: Теория вычислимости
Лекция: Вычислимые функции, полнота формализации понятия вычислимости, универсальная вычислимая функция
Нам уже стало понятно, чтобы работал некоторый алгоритм, нам необходимо закодировать число, слово, звук или видео какой-либо системой счисления. После проведенного перевода в другую систему счисления над числами можно производить некие действия, но в последствии результат получится целым.
То есть, какой бы алгоритм для некоторой функции не был бы выбран, он будет состоять и некоторых действий и приведет к ожидаемому результату. Такая функция называется вычислимой.
Если некоторый алгоритм позволяет найти решение по известным данным, то заданную функцию называют эффективно вычислимой.
Компьютер может выполнять абсолютно любую команду, если она прописана алгоритмом. Если он имеет подробный алгоритм, то сможет решить задачу любой сложности.
| Предыдущий урок | Следующий урок |
Оставить комментарий