Определить время выполнения программы по длине в битах?

Question

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

Ради простоты я буду приведите три примера программ / функций.

function one(s):
  return s

function two(s):
  while (True):
    print s

function three(s):
  for i from 0 to 10^10:
    print(s)

Итак, мои вопросы: есть ли способ формализовать длину программы (например, биты, используемые для ее описания) и также внутренняя память, используемая программой, для определения минимального / максимального количества времени / шагов, необходимых для определения, будет ли программа завершена или будет работать вечно.

Например, в первой функции программа не выполняет измените свою внутреннюю память и остановитесь через некоторое время.
Во втором примере программа работает вечно, но программа также не изменяет свою внутреннюю память. Например, если бы мы рассмотрели все программы с одинаковой длиной, как у второй программы, которые не изменяют свое состояние, не могли бы мы определить верхнюю границу шагов, которая, если превзойдет, мы могли бы заключить, что эта программа никогда не завершится? (Если нет, почему?)
В последнем примере программа изменяет свое состояние (переменная i). Таким образом, на каждом шаге верхняя граница может меняться.

[Короче] Сложность по Колмогорову предлагает способ нахождения (описательной) сложности объекта, такого как фрагмент текста. Я хотел бы знать, учитывая формальный способ описания пространства памяти, используемого программой (вычисляемый во время выполнения), если бы мы могли вычислить максимальное количество шагов, которое, если превзойдет, позволило бы нам знать, будет ли эта программа завершена или бежать вечно.

Наконец, я хотел бы предложить мне любой источник, который я мог бы найти полезным, и помочь мне выяснить, что именно я ищу.
Спасибо. (извините за мой английский sh, а не за мой родной язык. Надеюсь, я был понятен)

Answer 1

Если детерминированная c машина Тьюринга дважды вводит одну и ту же конфигурацию (которую мы можем обнаружить по сохранению следа конфигураций, которые мы видели до сих пор), то мы сразу же знаем, что ТМ будет l oop навсегда.

Если заранее известно, что машина Тьюринга c не может использовать больше чем фиксированную постоянную величину своей входной ленты, то ТМ должен явно остановить или в конечном итоге ввести некоторую конфигурацию, которую он уже посетил. Предположим, что TM может использовать не более k ленточных ячеек, алфавит ленты - T, а набор состояний - Q. Тогда есть (| T | +1) ^ k * | Q | уникальные конфигурации (количество строк более чем (T union blank) длиной k, умноженной на число состояний), и по принципу голубя мы знаем, что TM, который выполняет столько шагов, должен войти в некоторую конфигурацию, в которой он уже находился ранее.

one: поскольку нам говорят, что эта функция не использует внутреннюю память, мы знаем, что она либо останавливается, либо зацикливается навсегда.

two: поскольку нам говорят, что эта функция не использует внутреннюю память, мы знаем, что он либо останавливается, либо зацикливается навсегда.

три: поскольку нам дано указание, что эта функция использует только фиксированный объем внутренней памяти (например, 34 бита), мы можем сказать менее чем за 2 ^ 34 итераций l oop, остановится ли TM или гарантировано не для любых заданных входных данных.

Теперь, зная , сколько ленты будет использовать ТМ или сколько памяти будет использовать программа, это не проблема. ТМ может решить. Но если у вас есть oracle (например, человек, который смог сделать доказательство), который говорит вам правильную фиксированную верхнюю границу памяти, тогда проблема остановки решаема.