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

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

Текущая версия на 06:50, 4 мая 2023

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