Бесконечная программа без цикла и рекурсии

Можно ли написать бесконечную программу без циклов и рекурсии?

Конечно — для этого нужно совсем немного.

MODULE NoLoops;

  VAR i*: INTEGER;

  PROCEDURE A*; BEGIN i := (i + 1) MOD 40000000H              END A;
  PROCEDURE B*; BEGIN A;A;A;A;A;A;A;A;A;A;A;A;A;A;A;A;A;A;A;A END B;
  PROCEDURE C*; BEGIN B;B;B;B;B;B;B;B;B;B;B;B;B;B;B;B;B;B;B;B END C;
  PROCEDURE D*; BEGIN C;C;C;C;C;C;C;C;C;C;C;C;C;C;C;C;C;C;C;C END D;
  PROCEDURE E*; BEGIN D;D;D;D;D;D;D;D;D;D;D;D;D;D;D;D;D;D;D;D END E;
  PROCEDURE F*; BEGIN E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E;E END F;
  PROCEDURE G*; BEGIN F;F;F;F;F;F;F;F;F;F;F;F;F;F;F;F;F;F;F;F END G;
  PROCEDURE H*; BEGIN G;G;G;G;G;G;G;G;G;G;G;G;G;G;G;G;G;G;G;G END H;
  PROCEDURE I*; BEGIN H;H;H;H;H;H;H;H;H;H;H;H;H;H;H;H;H;H;H;H END I;
  PROCEDURE J*; BEGIN I;I;I;I;I;I;I;I;I;I;I;I;I;I;I;I;I;I;I;I END J;
  PROCEDURE K*; BEGIN J;J;J;J;J;J;J;J;J;J;J;J;J;J;J;J;J;J;J;J END K;
  PROCEDURE L*; BEGIN K;K;K;K;K;K;K;K;K;K;K;K;K;K;K;K;K;K;K;K END L;
  PROCEDURE M*; BEGIN L;L;L;L;L;L;L;L;L;L;L;L;L;L;L;L;L;L;L;L END M;
  PROCEDURE N*; BEGIN M;M;M;M;M;M;M;M;M;M;M;M;M;M;M;M;M;M;M;M END N;
  PROCEDURE O*; BEGIN N;N;N;N;N;N;N;N;N;N;N;N;N;N;N;N;N;N;N;N END O;
  PROCEDURE P*; BEGIN O;O;O;O;O;O;O;O;O;O;O;O;O;O;O;O;O;O;O;O END P;
  PROCEDURE Q*; BEGIN P;P;P;P;P;P;P;P;P;P;P;P;P;P;P;P;P;P;P;P END Q;
  PROCEDURE R*; BEGIN Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q;Q END R;
  PROCEDURE S*; BEGIN R;R;R;R;R;R;R;R;R;R;R;R;R;R;R;R;R;R;R;R END S;
  PROCEDURE T*; BEGIN S;S;S;S;S;S;S;S;S;S;S;S;S;S;S;S;S;S;S;S END T;
  PROCEDURE U*; BEGIN T;T;T;T;T;T;T;T;T;T;T;T;T;T;T;T;T;T;T;T END U;
  PROCEDURE V*; BEGIN U;U;U;U;U;U;U;U;U;U;U;U;U;U;U;U;U;U;U;U END V;
  PROCEDURE W*; BEGIN V;V;V;V;V;V;V;V;V;V;V;V;V;V;V;V;V;V;V;V END W;
  PROCEDURE X*; BEGIN W;W;W;W;W;W;W;W;W;W;W;W;W;W;W;W;W;W;W;W END X;
  PROCEDURE Y*; BEGIN X;X;X;X;X;X;X;X;X;X;X;X;X;X;X;X;X;X;X;X END Y;
  PROCEDURE Z*; BEGIN Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y;Y END Z;

BEGIN i := 0
END NoLoops.

Вызов NoLoops.Z; log.in(NoLoops.i), если бы смог, выполнялся бы на моём компьютере около 48 квадриллионов лет (4,8•10¹⁶). Для сравнения, возраст вселенной — около 13,8 миллиардов лет (1,38•10¹⁰), а самые долгоживущие звёзды — красные карлики протянут меньше 100 триллионов лет (10¹⁴). Cпор о том, является ли эта программа бесконечной, может вестись исключительно терминологически-философски.

Такие примеры показывают, что контроль за свойствами программы может быть сложней, чем кажется на первый взгляд. Язык программирования без циклов и рекурсии теоретически не является алгоритмически полным, но с практической точки зрения по своим возможностям может не уступать алгоритмически полным, потому что сама физика ставит ограничения сверху, которые не являются вычислимо недостижимими для «ограниченных» языков.

ChatGPT об этом коде.

Смотрите также

Бесконечное выполнение кода на препроцессоре C.