Формально об алгоритмах. Вычислительные модели/Задачи/ex-unsolvable-exists

Ссылки сюда (10) →

Маркеева Лариса 973б

Множество МТ при фиксированном алфавите входных и в выходных данных счетно. Следовательно, множество вычислимых на МТ функций так же счетно. Однако множество функций несчетно, если счетно. Следовательно, существуют невычислимые функции, так как множество функций (континуум), а вычислимых на МТ счетно.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.