Программирование только с помощью for

[Профессор Снэйп]

Lukin в сообщении #597683 писал(а):

...а вот ее работа выходит за рамки примитивной рекурсии. Интуиция подсказывает.
Или я не прав ?

С чего Вы взяли, что выходит?

$f(n) = n$, если что, примитивно рекурсивная функция. И $\varphi_n(x) = n$ тоже

[Lukin]

Профессор Снэйп в сообщении #597701 писал(а):

$f(n) = n$, если что, примитивно рекурсивная функция. И $\varphi_n(x) = n$ тоже

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

[Профессор Снэйп]

Lukin в сообщении #597707 писал(а):

...или все еще не понятно ?

Всё ещё непонятно.

Вы то предлагаете? Программа меняет себя и начинает исполнять свою изменённую копию?.. До тех пор, пока не произойдёт определённое изменение, сигнализирующее о том, что надо прекращать вычисления и давать ответ? Как Вы организуете такую передачу? Я, конечно, отстал от практики программирования довольно сильно, но мне кажется, что стандартные языки этого не разрешают.

Вы собираетесь перезаписывать текст исполняемой программы в памяти изнутри самой программы? Теоретически это сделать можно, вставляя в программу код низкого уровня, но это запрещённый приём!

-- Вс июл 22, 2012 02:26:56 --

И к квайнам всё это отношения не имеет. Квайн всего лишь воспроизводит собственный текст где-то на внешнем устройстве, а о передаче управления на сгенерированный код речи не идёт.

[Lukin]

Профессор Снэйп в сообщении #597738 писал(а):

Программа меняет себя и начинает исполнять свою изменённую копию?.. До тех пор, пока не произойдёт определённое изменение, сигнализирующее о том, что надо прекращать вычисления и давать ответ? Как Вы организуете такую передачу? Я, конечно, отстал от практики программирования довольно сильно, но мне кажется, что стандартные языки этого не разрешают.

Вот классический пример Куайн-программы на Delphi:

procedure selfprint;
 var a: array[1..11]of string; i: integer;
 begin
a[1]:=' procedure selfprint;';
a[2]:=' var a: array[1..11]of string; i: integer;';
a[3]:=' begin ';
a[4]:=' for i:=1 to 3 do writeln(a[i]);';
a[5]:=' for i:=1 to 11 do begin';
a[6]:='     write(chr(97), chr(91), i);';
a[7]:='     write(chr(93), chr(58), chr(61));';
a[8]:='     writeln (chr(39), a[i], chr(39),  chr(59));';
a[9]:=' end; ';
a[10]:=' for i:=4 to 11 do wtiteln(a[i]);';
a[11]:=' end. ';
 for i:=1 to 3 do writeln(a[i]);
 for i:=1 to 11 do begin
     write(chr(97), chr(91), i);
     write(chr(93), chr(58), chr(61));
     writeln (chr(39), a[i], chr(39),  chr(59));
 end;
 for i:=4 to 11 do wtiteln(a[i]);
 end;

При вызове этой процедуры она печатает свой текст.
Зарезервируем дополнительные строки в массиве

var a: array [1..13] of string;
…
a[12]:=’true’;
a[13]:=’здесь пишем имя процедуры (или сам код - тогда нужно больше строк зарезервировать в массиве), которую нам нужно выполнять в цикле’;
...
здесь вставляем имя процедуры или ее код, которые нам надо выполнять в цикле (он работает с внешними данными (переменными var, описанными перед всеми процедурами основной программы)

Все циклы увеличим на с 11 до 13 (или сколько нам нужно).

Пишем основную программу. В процедуру, которую нам нужно прогонять неопределенное число раз, до наступления некоего события, вставляем короткий код, который в случае наступления события меняет строку ‘a[12]=true’ в распечатке работы процедуры selfprint на ‘a[12]=false’. Из основной программы отслеживаем это событие после каждого вызова selfprint, либо в самой selfprint (это команда останова).
Получили аналог repeat,while,goto - цикл без заранее заданной границы.

Профессор Снэйп в сообщении #597738 писал(а):

Вы собираетесь перезаписывать текст исполняемой программы в памяти изнутри самой программы? Теоретически это сделать можно, вставляя в программу код низкого уровня, но это запрещённый приём!

Вам шашечки нужны или ехать ?
Вы предлагаете запретить программе работу со строками ?
Вы постоянно уточняете условия, можете ли Вы их сформулировать полно и окончательно ?

Профессор Снэйп в сообщении #597738 писал(а):

И к квайнам всё это отношения не имеет. Квайн всего лишь воспроизводит собственный текст где-то на внешнем устройстве, а о передаче управления на сгенерированный код речи не идёт

Укажите, в каком месте происходит передача управления на сгенерированный код в моем примере и просветите, как, в общем случае, по произвольному тексту алгоритма (в котором Ваши условия выполнены – язык программирования не содержит ни одного while, repeat, goto), Вы собираетесь отслеживать это самое условие ? Это алгоритмически разрешимая задача по Вашему ?

[Профессор Снэйп]

Lukin в сообщении #597770 писал(а):

Из основной программы отслеживаем это событие после каждого вызова selfprint, либо в самой selfprint (это команда останова).

Как Вы будете вызывать selfprint? Внутри какого-то цикла? Или изнутри самого селфпринта? Рекурсия, если что, запрещена, как явная, так и неявная (процедура $A$ вызывает процедуру $B$, процедура $B$ вызывает процедуру $A$).

Боюсь, что квайны тут совершенно не при чём. Печатать программе саму себя - это лишнее, идея в другом. Вы хотите вызывать процедуру, пока не наступит некоторое событие. Как Вы это сделаете?

Lukin в сообщении #597770 писал(а):

Вы постоянно уточняете условия, можете ли Вы их сформулировать полно и окончательно ?

Как видите, пока не уточняю Но цель темы, да, такая, прийти к точной формулировке. Моё участие в этой теме организовано по типу цикла repeat ... until

-- Вс июл 22, 2012 10:40:28 --

Lukin в сообщении #597770 писал(а):

Вы предлагаете запретить программе работу со строками ?

Нет, не предлагаю. При чём здесь это?

-- Вс июл 22, 2012 10:42:10 --

Lukin в сообщении #597770 писал(а):

Укажите, в каком месте происходит передача управления на сгенерированный код в моем примере и просветите, как, в общем случае, по произвольному тексту алгоритма (в котором Ваши условия выполнены – язык программирования не содержит ни одного while, repeat, goto), Вы собираетесь отслеживать это самое условие ? Это алгоритмически разрешимая задача по Вашему ?

Пока что Вы и пример не до конца написали. Просто скопипастили квайн-программу из сети и далее написали идею. Мне кажется, что это идея не реализуема допустимым образом. Если Вы считаете, что да - код в студию!

[Lukin]

to Профессор Снэйп:

Кажется я понял.
Вы запрещаете рекурсию на стадии создания программы, я же имел в виду, что для произвольного текста алгоритма, работающего со строками не ясно, есть внутри него рекурсия или нет.
Если заранее отрубить себе ноги, бессмысленно спрашивать, можно ли ходить…
Идея была вставить интерпретатор команд в текст процедуры и работать с собственным текстом, дописывая последующие исполняемые строки в ходе работы предыдущих.
Без явной или неявной рекурсии, похоже, не обойтись, я подумаю, можно ли ее сделать так, чтобы Вы не заметили

[Esp_]

Да прочитайте мое доказательство уже

[Lukin]

Да, почитал уже.
Тут более тонкий момент, в основаниях Вашего доказательства, в принятых исходных положениях.
Мне они не так очевидны, как Вам или Профессор Снэйп(у), в этом вся проблема.
Вы исходите из одних предположений и доказываете, что-то, а мне они не очевидны.
Если взять их с потолка, я согласен, вывод логичен, а если исходить из других аксиом, увы.
Т.к. дело касается бесконечной ленты, то исходные предположения, взятые с потолка, определяют ответ.
Лента бесконечна, поэтому ответы не имеют отношения к действительности (проверяемость нулевая).
Поэтому я всегда могу сказать, что доказывая не существование такого-то алгоритма, Вы ссылаетесь на "бесконечность ленты", т.е. на исходное, взятое с потолка предположение. В рамках этой аксиомы Вы правы, только не надо меня убеждать в ее очевидности. Мы "бесконечность ленты" по разному понимаем.

[Esp_]

Цитата:

Вы исходите из одних предположений и доказываете, что-то, а мне они не очевидны.

Можете привести в моем доказательстве предположение, которое нужно более детально пояснить?

[Профессор Снэйп]

Lukin в сообщении #597836 писал(а):

Идея была вставить интерпретатор команд в текст процедуры и работать с собственным текстом, дописывая последующие исполняемые строки в ходе работы предыдущих.

И делать это (дописывать строки и исполнять их) нужно до тех пор, пока не наступит некоторое событие. Без запрещённых циклов не обойтись, увы

-- Вс июл 22, 2012 18:36:27 --

Lukin в сообщении #597836 писал(а):

Кажется я понял.
Вы запрещаете рекурсию на стадии создания программы, я же имел в виду, что для произвольного текста алгоритма, работающего со строками не ясно, есть внутри него рекурсия или нет.

Рекурсии не должно быть в исходной программе. А в программе, создавамаемой из этой исходной программы, рекурсия допустима. Это нам никак не навредит, поскольку корректно работающий интерпритатор всё равно невозможно написать разрешёнными средствами.

Lukin в сообщении #597836 писал(а):

Если заранее отрубить себе ноги, бессмысленно спрашивать, можно ли ходить…

Но вполне осмысленно спросить, что можно сделать без ног. Например, рисовать и размахивать руками можно, а ходить нельзя. Здесь вопрос того же сорта: запретили определённые вещи и спрашивает, верно ли, что соблюдая эти запреты, можно вычислить все примитивно рекурсивные функции и только их. То, что все прф можно вычислить, очевидно. Сложная часть вопроса состоит в том, нельзя ли вычислить чего-нибудь лишнего.

Вашу идею я не принимаю. Мне кажется, что интерпретатор, выполняющий создаваемую по ходу программу до момента, пока мы не создадим команду остановки, допустимыми средствами (то есть не используя goto, запрещённые циклы и рекурсию), написать нельзя.

[Lukin]

Профессор Снэйп в сообщении #597893 писал(а):

Да, запрещаю. Все вызовы процедур должны быть "древовидными", на уровне синтаксиса, а не на уровне исполнения. Не знаю, понятно ли я выражаюсь.

Да, мне все понятно, в данном случае, вынужден, откланяться.
Конечно, "дерево" останется конечным, если изначально нет ничего "бесконечного".
Но есть "бесконечная лента", Вы это постулировали.
Мне понятно, что Вы приняли предположение, что на "бесконечности" дерево останется "деревом".
Я же не вижу никаких принципиальных ограничений (кроме изначально "отрубленных ног"), чтобы "дерево" на "бесконечности" не сослалось на само себя (что по-моему и есть "бесконечность"), иначе оно останется конечным "деревом".

В общем, я понимаю, как строится Ваше доказательство, в рамках принятых положений, и согласен с ними полностью, но по существу исходных положений не принимаю. Этот "фильтр" мне чужд, интуитивно, т.к. я не вижу (в Вашем определении) способа отличить бесконечное "дерево" от бесконечной "сети", кроме взятого с потолка желания его так себе представлять. У меня свои "пляски с бубном".

Не знаю, понятно ли я выражаюсь.

[Профессор Снэйп]

Lukin в сообщении #597901 писал(а):

Да, мне все понятно, в данном случае, вынужден, откланяться.

Я изменил своё сообщение. Перечитайте его заново.

-- Вс июл 22, 2012 19:08:48 --

Lukin в сообщении #597901 писал(а):

Не знаю, понятно ли я выражаюсь.

Вы выражаетесь в том духе, что моя задача Вам не нравится и Вы хотите решать не её, а другую задачу. Ну так заводите свою тему, в которой Вашу задачу будем обсуждать. А в этой теме мою.

-- Вс июл 22, 2012 19:10:02 --

Lukin в сообщении #597901 писал(а):

Да, мне все понятно, в данном случае, вынужден, откланяться.
Конечно, "дерево" останется конечным, если изначально нет ничего "бесконечного".
Но есть "бесконечная лента", Вы это постулировали.
Мне понятно, что Вы приняли предположение, что на "бесконечности" дерево останется "деревом".
Я же не вижу никаких принципиальных ограничений (кроме изначально "отрубленных ног"), чтобы "дерево" на "бесконечности" не сослалось на само себя (что по-моему и есть "бесконечность"), иначе оно останется конечным "деревом".

А вот здесь я ничерта не понял. Какая-то бессмыслица, на мой взгляд.

[Lukin]

Профессор Снэйп в сообщении #597903 писал(а):

Я изменил своё сообщение. Перечитайте его заново…
Рекурсии не должно быть в исходной программе. А в программе, создавамаемой из этой исходной программы, рекурсия допустима. Это нам никак не навредит, поскольку корректно работающий интерпретатор всё равно невозможно написать разрешёнными средствами.

"Разрешенными" ? Это какими ? Если у него "бесконечная" лента, то и разницы нет.
Если несколько процедур имеют доступ к бесконечной ленте и ссылаются на данные, как на коды (замечу, их всегда, в конечном смысле, можно сделать разными на некое число прописываемое в конце процедуры, т.е. рекурсии не будет), как Вы определите, конечны ли выдаваемые ими данные ?
В каждый момент обращения данные конечны, но в последовательности обращений к ним, они могут неограниченно возрастать.

Esp_ в сообщении #597892 писал(а):

Можете привести в моем доказательстве предположение, которое нужно более детально пояснить?

Тезис Черча-Тьюринга Вас устроит ?

Профессор Снэйп в сообщении #597903 писал(а):

Lukin в сообщении #597901 писал(а):

Не знаю, понятно ли я выражаюсь.

Вы выражаетесь в том духе, что моя задача Вам не нравится и Вы хотите решать не её, а другую задачу. Ну так заводите свою тему, в которой Вашу задачу будем обсуждать. А в этой теме мою.

Покидая ВАШУ тему, снимаю шляпу...

Профессор Снэйп в сообщении #597903 писал(а):

А вот здесь я ничерта не понял. Какая-то бессмыслица, на мой взгляд.

Ничего добавить не могу, бессмыслицы в Ваших рассуждениях не вижу, все корректно, но под "бесконечнстью" ленты смею понимать нечто иное.

[Esp_]

Цитата:

Тезис Черча-Тьюринга Вас устроит ?

А как он связан с моим доказательством?

Или же вы хотите, чтобы я вам этот Тезис пояснил?

[alexBlack]

Профессор Снэйп в сообщении #596306 писал(а):

Отменим в языке программирования циклы while/repeat, оставим только цикл for, количество итераций которого вычисляется до начала выполнения цикла.

А если смоделировать while взяв заведомо бОльшее количество итераций ?
После выполнения цикла for мы либо получим результат, либо будет известно, что за такое количество итераций ответ недостижим.

(пример)

type
   trq = packed record
      m, n : integer;
   end;

const max = 10000;
var acm : array [0..max, 0..max] of integer;
    stack : array [0..1000] of trq;
    head : integer;

procedure Ackermann(am, an:integer);
var dummy, m, n, k:integer;
begin
   head := 0;
   stack[head].m := am;
   stack[head].n := an;
   for dummy := 0 to 100000000 do begin
      if head >= 0 then begin
         m := stack[head].m;
         n := stack[head].n;

         if acm[m, n] > 0 then begin
            dec(head);
         end else

         if m = 0 then begin
            acm[m, n] := n+1;
            dec(head);
         end else

         if n = 0 then begin
            if acm[m-1, 1] > 0 then begin
               acm[m, n] := acm[m-1, 1];
               dec(head);
            end else begin
               inc(head);
               stack[head].m := m-1;
               stack[head].n := 1;
            end;
         end else

         begin
            k := acm[m, n-1];
            if k <= 0 then begin
               inc(head);
               stack[head].m := m;
               stack[head].n := n-1;
            end else begin
               if acm[m-1, k] > 0 then begin
                  acm[m, n] := acm[m-1, k];
                  dec(head);
               end else begin
                  inc(head);
                  stack[head].m := m-1;
                  stack[head].n := k;
               end;
            end;
         end;
      end;
   end;
   if acm[am, an] > 0
   then writeln('Ackermann(', am, ',', an, ') = ', acm[am, an])
   else writeln('I can''t compute Ackermann(', am, ',', an, ')');
end;