Как следствие теоремы Райс , невозможно определить, что есть что.
Доказательство: пусть L будет выходом нормального ГСЧ. Пусть L 'будет L, но со всеми удаленными последовательностями длины> = 3. Некоторые ТМ распознают L ', но некоторые нет. Следовательно, по теореме Райс определение, принимает ли ТМ L ', не разрешимо.
Как уже отмечали другие, вы можете сделать утверждение вроде: «Он выполнил N шагов без повторения три раза», но вы никогда не сможете совершить скачок к «он будет никогда повторять цифра три раза. " Точнее, существует хотя бы одна машина, для которой вы не можете определить, соответствует ли она этому критерию.
Предостережение: если бы у вас был действительно случайный генератор (например, ядерный распад), вполне возможно, что теорема Райс не будет применима. Моя интуиция заключается в том, что теорема все еще справедлива для этих машин, но я никогда не слышал, чтобы она обсуждалась.
РЕДАКТИРОВАТЬ : вторичное доказательство. Предположим, что P(X) с высокой вероятностью определяет, принимает ли X L'. Мы можем построить (бесконечное число) программ F, таких как:
F(x): if x(F), then don't accept L'
else, accept L'
P не может определить поведение F(P). Более того, скажем, P правильно предсказывает поведение G. Мы можем построить:
F'(x): if x(F'), then don't accept L'
else, run G(x)
Таким образом, для каждого хорошего случая должен существовать хотя бы один плохой случай.