Формально об алгоритмах. Вычислительные модели/Задачи/ex-unsolvable-exists — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | + | Маркеева Лариса 973б | |
| − | + | ||
| − | [[ | + | Множество МТ при фиксированном алфавите входных и в выходных данных счетно. Следовательно, множество вычислимых на МТ функций так же счетно. Однако множество функций <math>f:N\rightarrow N</math> несчетно, если <math>N</math> счетно. Следовательно, существуют невычислимые функции, так как множество функций <math>f:N\rightarrow N</math> (континуум), а вычислимых на МТ счетно. |
| − | + | ||
| + | |||
| + | [[Категория:На проверку]] | ||
Версия 11:59, 8 октября 2014
Маркеева Лариса 973б
Множество МТ при фиксированном алфавите входных и в выходных данных счетно. Следовательно, множество вычислимых на МТ функций так же счетно. Однако множество функций несчетно, если счетно. Следовательно, существуют невычислимые функции, так как множество функций (континуум), а вычислимых на МТ счетно.