Концепция лучше всего иллюстрируется примерами и сравнением с рекурсивными наборами и сравнением разных определений. Поэтому я сделаю именно это: сначала я приведу вам примеры, а затем приведу разные (но эквивалентные) определения.
Во-первых, обратите внимание, что технически мы применяем прилагательное «рекурсивно перечислимый» (также известный как «полуразрешимый») к множествам натуральных чисел. Но это прилагательное может также применяться к набору целых чисел, к набору пар целых чисел, к набору строк Unicode. Обратите внимание, что любые из этих вещей (целые числа, пары целых чисел, строки Unicode) могут храниться в памяти компьютера. (Вещи, которые не могут быть сохранены в памяти компьютера, включают в себя произвольные (с бесконечной точностью) действительные числа и бесконечные последовательности от 0 до 1 с)
Пример 1: множество всех простых чисел
Вы можете написать алгоритм, который принимает в качестве входных данных натуральное число и возвращает ответ «да» или «нет» (да, что означает «да, этот ввод простое», но не означает «нет, этот ввод не простое»). ). Этот алгоритм легко написать. Очень просто, если вы не потрудитесь оптимизировать для повышения производительности. Поскольку вы можете написать алгоритм, который всегда заканчивается и дает ответ «да» или «нет», набор всех простых чисел называется разрешимым набором (также известным как рекурсивный набор ). Это называется разрешимым, потому что вы можете решить , является ли натуральное число простым или нет. Обратите внимание, что если вы хотите доказать, что набор является разрешимым набором, вам просто нужно придумать алгоритм, который всегда завершается и дает правильный ответ, и вам не нужно оптимизировать производительность. Давайте не будем вдаваться в то, почему это называется рекурсивным.
Пример 2. простой разрыв - это разница между двумя последовательными простыми числами. Например, 13 - простое число, а следующее простое число - 17, и поэтому их разность 4 - это простое число. Наш второй пример - это множество всех простых пробелов.
Можете ли вы написать алгоритм, чтобы проверить, является ли число простым пробелом или нет? Как насчет следующего псевдокода?
input: x
set i to 1
loop
check primeness of i, i+1, ..., i+x
if only i and i+x among them are primes, return yes.
otherwise, increment i by 1 and go to start of loop
Алгоритм в псевдокоде имеет некоторые хорошие и некоторые плохие.
Плохое: оно никогда не закончится, если входное значение не будет простым пробелом. Он никогда не возвращает ответ №.
Хорошо: если он возвращает ответ «да», вы точно знаете, что входной сигнал представляет собой простой пробел, и наоборот.
Этот набор является примером полуразрешимого набора (также известного как рекурсивно перечислимый набор ). Алгоритм всегда даст вам положительное подтверждение, если вы введете простой пробел и подождите достаточно долго, но алгоритм никогда не даст вам отрицательного подтверждения, если вы введете число, которое не является простым пробелом.
Определение: множество является полуразрешимым множеством, если существует алгоритм, который принимает входные данные и который либо возвращает да, либо возвращает нет, либо никогда не возвращает (из-за бесконечного цикла или ошибки), и если этот алгоритм возвращает да всякий раз, когда задан вход набор, и если этот алгоритм никогда не возвращает да, если задан вход, не входящий в набор.
Все кружки - эллипсы, а все разрешимые множества - полурешаемые множества.
Задумавшись, вы можете понять, что разрешено ли алгоритму возвращать no, иногда правильно, на самом деле не имеет значения для определения в конце. С большим вниманием вы также можете понять, что допускать ошибку или нет, не имеет значения и для определения. Эти реализации позволяют нам прийти к эквивалентному, более простому, но немного менее интуитивному определению:
Менее интуитивное определение: набор является полуразрешимым набором, если существует алгоритм, который принимает входные данные, и если этот алгоритм возвращает (то есть программа завершается) тогда и только тогда, когда ему дан вход в наборе.
Теперь поговорим о списочных наборах. Набор - это список , если есть алгоритм, который печатает все элементы в наборе (и ничего больше). Конечно, этот алгоритм никогда не завершится, если он должен печатать бесконечно много элементов. С некоторыми мыслями вы можете понять, что всякий раз, когда у вас есть алгоритм для печати всех чисел в наборе, иногда печатая одно и то же число более одного раза, вы можете изменить алгоритм так, чтобы он печатал все числа только один раз. Обратите внимание, что определение НЕ говорит о том, что алгоритм должен сначала печатать наименьший элемент, а затем второй наименьший элемент и т. Д. Почему я говорю о списочных наборах?
Теорема. Множество является списочным множеством тогда и только тогда, когда оно является полуразрешимым множеством.
Давайте не будем вдаваться в то, почему это так (может быть, зададим для этого SO-вопрос?), Но позвольте мне упомянуть, что это является причиной фразы «рекурсивно перечислимый»: вы можете перечислять множество в том смысле, что вы может перечислить все элементы один за другим, и «рекурсивно» означает просто «с алгоритмом».
Как насчет примера, который не включает числа?
Пример 3. Набор всех строк ASCII, который является определением функции Python без аргументов и гарантированно будет возвращен. (Для простоты давайте также исключим функции Python, вызывающие библиотеки, выполняющие некоторые аппаратные функции)
Этот набор является полуразрешимым набором, потому что вы можете создать алгоритм полуопределения. Алгоритм просто должен эмулировать Python, чтобы запустить функцию Python, а затем дождаться его завершения. Если функция Python когда-либо возвращается в вашей эмуляции, ваш алгоритм возвращает да. Это алгоритм. Можем ли мы сделать лучше, чем этот алгоритм? Да, создать алгоритм, который обнаруживает бесконечный цикл в некоторых случаях и возвращает нет. Можете ли вы придумать алгоритм, который никогда не сможет обнаружить бесконечный цикл? Если вы можете придумать такой алгоритм, этот набор будет решаемым. К сожалению, такого алгоритма нет, и мы можем это доказать.
Пример финала. Когда Сталин был у власти, набор хороших политик советского правительства был подобен полуразрешимому набору. Был кто-то, кто был одним из советников правительства. Сталин спрашивал его: «У меня есть идея для новой политики. Идея - бла-бла-бла. Это хорошая политика?» Простой вопрос да или нет. Он ответил бы «да» после того, как несколько дней анализа показали, что политика действительно была хорошей. Что если политика была плохой? У него был принцип «не лги никогда», но он также знал, что происходит с теми, кто говорит Сталину «нет». Всякий раз, когда Сталин говорил: «Вы решили, хороша ли политика? Прошли месяцы с тех пор, как я спрашивал ваше мнение по этому поводу». и он говорил: «Дайте мне больше времени подумать, товарищ Сталин».