Дело в том, что Профессор запрещает использовать рекурсию в коде программы и в то же время, утверждает, что интерпретатор команд (соответственно, компилятор) не может быть написан на одних только «разрешенных» циклах:
Рекурсии не должно быть в исходной программе. А в программе, создаваемой из этой исходной программы, рекурсия допустима. Это нам никак не навредит, поскольку корректно работающий интерпритатор всё равно невозможно написать разрешёнными средствами.
Вообще-то
исходной программой является не код на Delphi, С++ и т.д., а именно откомпилированный код, даже не ассемблер, а машинные коды процессора. Эти коды по определению используют «запрещенные» методы.
Соответственно, вопрос сводится к следующему: любой ли код на Delphi, С++ и т.д., с указанными ограничениями (без repeat,goto,while, рекурсии), всегда переводится в машинные коды «правильно», так, чтобы не образовывалось «запрещенных» циклов.
Т.е. это вопрос о «совершенстве» интерпретатора(компилятора).
Существует ли такой код, который при подаче на данный компилятор, так преобразуется в машинные коды, что их исполнение вызовет зависание программы (бесконечный цикл).
Мне очевидно, что такой код существует. Причина именно в том, что
исходный машинный код всегда содержит в себе «запрещенные» команды. Если бы процессор не поддерживал такие «запрещенные» команды бесконечного цикла, его можно было бы выбрасывать после каждого «исполнения» какой-либо программы.
Т.е. в самом исходном понятии алгоритма уже заложена "запрещенная" бесконечная повторяемость.
Что касается рекурсии.
Зная, как компилятор преобразует код на Delphi в «исходный код» и по каким адресам размещает его в памяти, внутри самой процедуры можно получить доступ к определенной части собственного кода и изменить ее.
Утрированный пример (в предположении, что команды Delphi и есть машинные коды):
procedure Example;
var x,y:integer; str:string;
begin
x:=GetAddress (Example); получили абсолютный адрес кода процедуры Example;
str:=Read(x+8,3); прочитали восьмую строку кода, начиная с третьего символа ;
str:=IntToStr(StrToInt(str)+1); изменили восьмую строку кода с третьего символа;
Write (x+8,3); записали измененный код на место;
N:=0; - это и есть восьмая строка кода, а меняться будет 0 на 1, 1 на 2 и т.д.
Example; вызываем уже измененную процедуру Example, можно обозначить ее Example1.
End; конец.
Для тех, кто не в танке, ясно, что
это не рекурсия, т.к. строго формально, рекурсия - это цикличный вызов
той же самой процедуры.
А здесь, хоть исполняемая процедура и имеет то же имя, как и рекурсивная (кстати, можно и имя каждый раз менять), фактически это уже
другая процедура, т.к. команды 'N:=0' в ней уже нет, а есть команда 'N:=1', а, как известно, процедуры содержащие разные команды, считаются разными.
", "множество перечисленных к шагу