Рекурсивно разрешимый язык, принятие бесконечного языка

Question

Поэтому я понимаю, что рекурсивно-разрешимые языки - это языки, на которых мы можем построить машину Тьюринга так, чтобы с учетом входных данных этого языка машина Тьюринга всегда принимала и останавливала, либо отклоняла и останавливала. Что меня смущает, так это языки, которые могут расти до бесконечности. Скажем, например, у нас есть язык L = {0^p | p простое число}. Таким образом, мы можем написать алгоритм, который решает, является ли число простым или нет в линейном пространстве. Таким образом, я понимаю, что, поскольку этот алгоритм либо говорит нам, что число простое, либо не простое, то L должно быть рекурсивно разрешимым, верно? Но так как p не связан каким-либо фиксированным числом, он может перейти в бесконечность правильно? Так правильно ли предположить, что мой алгоритм может работать технически вечно, не принимая и не отклоняя ввод, и в этом случае наш L не будет рекурсивно разрешимым и будет рекурсивно перечислимым?

Answer 1

1. Да, язык унарных слов простой длины является разрешимым. Как вы уже сказали, это может быть сделано даже в пространстве, линейном по размеру ввода.
2. Да, язык содержит слова произвольной длины. Но говорить, что р уходит в бесконечность, вводит в заблуждение. Он принимает все возможные целочисленные значения, но без какого-либо порядка. Бесконечность не является целым числом, и, поскольку в определении множества нет порядка, нет никакой тенденции идти к бесконечности.
3. Нет, вы не можете предполагать, что алгоритм работает вечно. Он принимает не все строки, а только одну. И каждая строка имеет конечную длину, поэтому алгоритм завершится для каждой из них. Тот факт, что существует бесконечно много разных возможных входов, здесь не имеет значения.