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

Версия 01:33, 26 декабря 2014

Докажите, что существуют невычислимые по Тьюрингу функции y=f(x), используя мощностные соображения.

@@ Строка 1: / Строка 1: @@
-Маркеева Лариса 973б
+Докажите, что существуют невычислимые по Тьюрингу
+функции <tt>y=f(x)</tt>, используя мощностные соображения.
-Множество МТ при фиксированном алфавите входных и в выходных данных счетно. Следовательно, множество вычислимых на МТ функций так же счетно. Однако множество функций <math>f:N\rightarrow N</math> несчетно, если <math>N</math> счетно. Следовательно, существуют невычислимые функции, так как множество функций <math>f:N\rightarrow N</math> (континуум), а вычислимых на МТ счетно.
+[[Category:Решенные задачи]]
+<!--Вообще-то, решения уже есть-->
-[[Категория:На проверку]]