Как написать программу для обнаружения бесконечного цикла в другой программе

Question

Во время написания программы я часто сталкиваюсь с бесконечным циклом.

Как мне написать программу, которая принимает в качестве входных данных другую программу и определяет, существует ли бесконечный цикл или нет?

Answer 1

Вы не можете. И под этим я не имею в виду «это действительно сложно». Я имею в виду «это хорошо известная проблема в области компьютерных наук, которую люди пытаются решить с момента создания этой области, и если бы вы могли ее решить, вы бы сразу стали всемирно известными».

Алан Тьюринг доказал, что его невозможно решить, и никто не смог его опровергнуть, поэтому я говорю: «Если бы вы могли решить эту проблему, вы были бы всемирно известны».

См. Проблема остановки .