Почему невычислимых функций больше, чем вычислимых?

29

Я сейчас читаю книгу по алгоритмам и сложности. В данный момент я читаю о вычислимых и невычислимых функциях, и моя книга утверждает, что есть гораздо больше функций, которые не вычислимы, чем вычислимы, на самом деле, большинство говорит, что они не вычислимы. В каком-то смысле я могу интуитивно принять это, но книга не дает формального доказательства и не дает подробного описания этой темы.

Я просто хотел увидеть доказательство / позволить кому-то здесь прояснить это / более четко понять, почему существует так много невычислимых функций, чем вычислимых.

hsalin
источник
При сравнении двух бесконечных множеств семантика «больше» должна быть пересмотрена.
Рафаэль

Ответы:

31

Являются счетно множество вычислимых функций:

Каждая вычислимая функция имеет как минимум один алгоритм. Каждый алгоритм имеет конечное описание с использованием символов из конечного набора, например, конечных двоичных строк с использованием символов . Число конечных двоичных строк, обозначаемых { 0 , 1 } ∗, является счетным (т. Е. Таким же, как число натуральных чисел N ).{0,1}{0,1}*N

Следовательно, может быть не более счетного числа вычислимых функций. Существует как минимум счетное множество вычислимых функций, поскольку для каждого постоянная функция f ( x ) = c вычислима.с{0,1}*е(Икс)знак равнос

Другими словами, существует соответствие между:

  • множество вычислимых функций,
  • набор алгоритмов,
  • , множество конечных строк из { 0 , 1 } , и{0,1}*{0,1}
  • , множество натуральных чисел.N

С другой стороны, существует бесчисленное множество функций над строками (или натуральными числами). Функция (или f : { 0 , 1 }е:NN ) назначает значение для каждого входа. Каждое из этих значений может быть выбрано независимо от других. Таким образом, существует N N = 2 N возможных функций. Количество функций над натуральными числами равно количеству действительных чисел.е:{0,1}*{0,1}*NNзнак равно2N

Поскольку только счетное число функций вычислимо, большинство из них не являются. На самом деле количество невычислимых функций также .2N

Если вы хотите представить это интуитивно, подумайте о натуральных числах и действительных числах или о конечных двоичных строках и бесконечных двоичных строках. Существует намного больше действительных чисел и бесконечных двоичных строк, чем натуральных чисел и конечных строк. Другими словами, (для доказательства этого факта см . Диагональный аргумент Кантора и кардинальную арифметику ).N<2N

Кава
источник
Хороший ответ! То, что я не понимаю (я мог бы упустить что-то тривиальное здесь), как вы получите NNзнак равно2N ?
hsalin
Это кардинальная арифметика. Запишите натуральные числа в бесконечной последовательности натуральных чисел в двоичном виде, что должно дать интуицию.
Каве
Почему это предположение верно: «Каждый алгоритм имеет конечное описание с использованием символов из конечного набора»? Почему алгоритм не может иметь бесконечного описания?
Роланд Пихлакас
@RolandPihlakas, который является частью определения алгоритма (если вы предпочитаете, компьютерную программу).
Каве
9

Вот «явная» конструкция несчетного числа невычислимых булевых функций. Пусть - некоторая фиксированная невычислимая булева функция, скажем, характеристическая функция задачи остановки. Рассмотрим множество функций F = { f : N{ 0 , 1 } : x N , f ( 2 x ) = K ( x ) } .К

Fзнак равно{е:N{0,1}:ИксN,е(2Икс)знак равноК(Икс)},
Каждый невычислим, а F несчетен.еFF

р

гзнак равно{г:N{0,1}:NNмN,г(м)знак равнор(м),}
ггргг

Таким образом, существует множество невычислимых функций, поскольку у нас «бесконечно много» степеней свободы - фактическая бесконечность, а не «потенциальная» бесконечность, как в вычислимом случае.

Юваль Фильмус
источник