Здравствуйте, gandjustas, Вы писали:

DR>>Не все функции вычислимы на машине Тьюринга. Более того, почти все функции невычислимы.

G>Приведи пример чтоли.

Пример чего? Невычислимой по Тьюрингу функции? Да любая функция, которая принимает на вход инстанс неразрешимой decision problem и выдает результат (да/нет). Ну или классический пример — функция вычисления Kolmogorov complexity.

Что касается второй части утверждения Don Reba, то это вполне очевидно: число всех возможных МТ счетно (множество МТ отображается на множество натуральных чисел), в то время как множество функций на вещественных числах, разумеется, несчетно. Отсюда вывод: почти все функции невычислимы. Аналогично: почти все вещественные числа невычислимы и т.д.