Просто добавьте к тому, что сказал Пол Г.Д., помните, что вы запускаете все программы длиной или меньше и позволяете им работать не более i секунд. Возможно, есть программа, которая получает правильный ответ длиной 100 символов, но для ее запуска требуется 120 секунд. Вызов этой программы P . На i = 100 вы проверите эту программу, но она слишком долго запускается, поэтому вы ее отбрасываете. После проверки всех программ длины 100 вы обнаружите, что ни одна из них не дает правильного ответа, поэтому вы пробуете программы длины 101 и все программы, которые вы пробовали ранее . Таким образом, вы повторите попытку PiiPi=100101 Pпрограмма, которая (мы знаем) даст вам правильный ответ, но она все еще занимает слишком много времени, поэтому вы отказываетесь от нее. Мы продолжаем этот процесс, пока не достигнем . Затем мы пробуем все программы длиной ≤ 120 , и когда мы добираемся до P, мы даем ему поработать достаточно долго, чтобы дать правильный ответ. Затем мы останавливаемся - мы нашли алгоритм, который хотели. Итерация, на которой мы работаем, - это i = 120 , потому что, хотя длина программы P меньше (мы бы написали | P | = 100 ), нам пришлось подождать, пока количество времени, которое потребовалось, составило 120 секунд ( s = 120i=120≤120Pi=120P|P|=100s=120). Таким образом , просто означает максимальную длину программы P и количество времени, которое потребовалось для запуска s .i=max{|P|,s}Ps
Ps |P| si<|P|i<s
Обратите внимание, что этот метод поиска гарантированно даст вам ответ, только если он есть; не гарантируется найти самый короткий или быстрый ответ. Причина этого должна быть очевидна, если учесть, что процесс завершается, как только он находит программу, которая дает правильный ответ.