Я сейчас читаю книгу по алгоритмам и сложности. В данный момент я читаю о вычислимых и невычислимых функциях, и моя книга утверждает, что есть гораздо больше функций, которые не вычислимы, чем вычислимы, на самом деле, большинство говорит, что они не вычислимы. В каком-то смысле я могу интуитивно принять это, но книга не дает формального доказательства и не дает подробного описания этой темы.
Я просто хотел увидеть доказательство / позволить кому-то здесь прояснить это / более четко понять, почему существует так много невычислимых функций, чем вычислимых.
Ответы:
Являются счетно множество вычислимых функций:
Каждая вычислимая функция имеет как минимум один алгоритм. Каждый алгоритм имеет конечное описание с использованием символов из конечного набора, например, конечных двоичных строк с использованием символов . Число конечных двоичных строк, обозначаемых { 0 , 1 } ∗, является счетным (т. Е. Таким же, как число натуральных чисел N ).{ 0 , 1 } { 0 , 1 }* N
Следовательно, может быть не более счетного числа вычислимых функций. Существует как минимум счетное множество вычислимых функций, поскольку для каждого постоянная функция f ( x ) = c вычислима.c ∈ { 0 , 1 }* е( х ) = с
Другими словами, существует соответствие между:
С другой стороны, существует бесчисленное множество функций над строками (или натуральными числами). Функция (или f : { 0 , 1 }е: N → N ) назначает значение для каждого входа. Каждое из этих значений может быть выбрано независимо от других. Таким образом, существует N N = 2 N возможных функций. Количество функций над натуральными числами равно количеству действительных чисел.е: { 0 , 1 }*→ { 0 , 1 }* NN= 2N
Поскольку только счетное число функций вычислимо, большинство из них не являются. На самом деле количество невычислимых функций также .2N
Если вы хотите представить это интуитивно, подумайте о натуральных числах и действительных числах или о конечных двоичных строках и бесконечных двоичных строках. Существует намного больше действительных чисел и бесконечных двоичных строк, чем натуральных чисел и конечных строк. Другими словами, (для доказательства этого факта см . Диагональный аргумент Кантора и кардинальную арифметику ).N < 2N
источник
Вот «явная» конструкция несчетного числа невычислимых булевых функций. Пусть - некоторая фиксированная невычислимая булева функция, скажем, характеристическая функция задачи остановки. Рассмотрим множество функций F = { f : N → { 0 , 1 } : ∀ x ∈ N , f ( 2 x ) = K ( x ) } .К
Таким образом, существует множество невычислимых функций, поскольку у нас «бесконечно много» степеней свободы - фактическая бесконечность, а не «потенциальная» бесконечность, как в вычислимом случае.
источник