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

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

Отменим в языке программирования циклы while/repeat, оставим только цикл for, количество итераций которого вычисляется до начала выполнения цикла. Запретим исскуственно организовывать циклы типа while при помощи goto (можно на всякий случай вообще запретить goto). Остальное оставим, в том числе и рекурсию, кроме рекурсии, возможности для рекурсивного вызова тоже уберём.

Насколько очевиден тот факт, что функции (из $\mathbb{N}$ в $\mathbb{N}$), вычисление которых можно запрограммировать в этом языке - это, в точности, примитивно рекурсивные функции?

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

[Xaositect]

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

Остальное оставим, в том числе и рекурсию

Можно же реализовать оператор $\mu$ с помощью рекурсии:

def mu_f(y):
    return go(0, y)

def go(x, y):
    if f(x, y) == 0:
        return x
    else:
        return go(x + 1, y)

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

Xaositect в сообщении #596370 писал(а):

Можно же реализовать оператор $\mu$ с помощью рекурсии

Это читерство

Ну да, нужно постановить, чтобы рекурсивный вызов должен каждый раз производится с уменьшением некоторого заранее выбранного параметра.

-- Ср июл 18, 2012 02:42:05 --

А тогда его можно и через for смоделировать... Да, нельзя рекурсию! Зачеркну сейчас в условии.

[Xaositect]

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

Ну да, нужно постановить, чтобы рекурсивный вызов должен каждый раз производится с уменьшением некоторого заранее выбранного параметра.

Тогда достаточно очевидно. Такую рекурсию можно в цикл for развернуть.

[Pavia]

Сразу скажу вопроса не понял.
Если что то вот вам ответ если $N$ равно бесконечности то мы можем сделать на таком языке автомат известный как машина Тьюринга, а на нём реализовать нужный нам функцианал хотябы в виде интерпретатора. $N$ можно взять большим и всегда найдётся такое что больше необходимого так как память бесконечна.

[Esp_]

Ну, это очевидно, поскольку есть памяти можно соорудить стек.

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

Pavia в сообщении #596514 писал(а):

...мы можем сделать на таком языке автомат известный как машина Тьюринга

Да ну?

И как Вы это будете реализовывать? У Вас нет ни goto, ни цикла с выходом по условию! Машина Тьюринга же работает, пока не перейдёт в состояние остановки. У неё есть тело элементарного цикла: посмотреть на состояние считывающего устройства, на символ в текущей позиции ленты, в зависимости от сочетания этих двух данных переписать символ и сдвинуться. И этот элементарный цикл повторяется, пока машина не переходит в состояние остановки. Как Вы собираетесь выходить из него?

[Pavia]

Цитата:

Как Вы собираетесь выходить из него?

А этого в условии не было.
Из конечного состояния буду переходить в конечное. Оно так и будит циклически в нем находиться пока цикл не закончится.

1) Если цикл бесконечный проблем нет.
2) Если цикл конечный, то надо взять просто очень большое число шагов которое будет заведомо больше или равно нашему алгоритму. Когда цикл завершится тогда и произойдёт выход.

[Esp_]

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

Цитата:

количество итераций которого вычисляется до начала выполнения цикла

Вы, правы, не совсем очевидно. Вот это предложения я проглядел. Беру свои слова про стек обратно.

Очевидно, кто класс примитивно рекурсивных функциий реализуем. Реализуем ли оператор минимизации - нужно время, чтобы подумать.

-- Пт июл 20, 2012 12:48:19 --

Подумал: Пусть существует конечная программа $P$, с $n$ вложенными циклами, тогда количество итераций такой программы вычисляется примитивно рекурсивной функцией $f1$. Существует частично рекурсивная функция $f2$, которая начиная с некоторого своего аргумента $y$ для любых оставшихся аргументов аргументов принимает значение 0 только если $y > f1(...)$.

Остается лишь ее построить: ну лично мне кажется, что существование такой функции $f2$ очевидно.
Ну вот, поэтому, да, класс ЧРФ такими программами описать нельзя.

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

Pavia в сообщении #597175 писал(а):

...надо взять просто очень большое число шагов которое будет заведомо больше или равно нашему алгоритму.

Число больше алгоритма! Мой моск разлетается по окрестностям со скоростью пять квадратных метров...

[Portnov]

Профессор Снэйп, а откуда такая задача, если не секрет?

Мне просто эти рассуждения напомнили рассуждения о видах "хорошей" рекурсии (гуглить по словам Bananas, Lenses and Barbed Wire). По-моему, утверждения о завершаемости или незавершаемости разных классов программ как-то естественнее разбираются в терминах ФП (всякие там лямбда-исчисления и теории типов), чем в терминах машин Тьюринга и алгоритмов.

[bin]

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

Pavia в сообщении #596514 писал(а):

...мы можем сделать на таком языке автомат известный как машина Тьюринга

Да ну?

И как Вы это будете реализовывать? У Вас нет ни goto, ни цикла с выходом по условию! Машина Тьюринга же работает, пока не перейдёт в состояние остановки. У неё есть тело элементарного цикла: посмотреть на состояние считывающего устройства, на символ в текущей позиции ленты, в зависимости от сочетания этих двух данных переписать символ и сдвинуться. И этот элементарный цикл повторяется, пока машина не переходит в состояние остановки. Как Вы собираетесь выходить из него?

Если правильно понял условие, нет и простого условного оператора? Если так, то ответ "Нет", а если условный оператор разрешен, то ИМХО ответ "Да": сошлюсь на Википедию:

Цитата:

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

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

bin в сообщении #597603 писал(а):

Если правильно понял условие, нет и простого условного оператора?

Нет, Вы неправильно поняли. Простой условный оператор вида if ... then { ... } else { ... } есть.

Portnov в сообщении #597575 писал(а):

Профессор Снэйп, а откуда такая задача, если не секрет?

Мне просто эти рассуждения напомнили рассуждения о видах "хорошей" рекурсии (гуглить по словам Bananas, Lenses and Barbed Wire). По-моему, утверждения о завершаемости или незавершаемости разных классов программ как-то естественнее разбираются в терминах ФП (всякие там лямбда-исчисления и теории типов), чем в терминах машин Тьюринга и алгоритмов.

Задача, скажем так, из практики преподавания. И даже скорее не задача, а просто вопрос. Тема для обсуждения, так сказать.

Я читаю курс "теория алгоритмов" в НГУ. К сожалению, это семестровый курс, и читается в первом семестре. Фактически вчерашним школьникам. Тами что про лямбда-исчисление и теорию типов рассказывать бесполезно, не поймут. А вот машины Тьюринга попроще, их понимают

По ходу курса я сначала рассказываю про примитивно рекурсивные функции, потом про частично рекурсивные. В конце курса возникает функция Аккермана, как пример функции, рекурсивной, но не примитивно рекурсивной. Ну и, естественно, по ходу курса время от времени ведётся неформальное обсуждение. В частности, говорится, что программирование на разных формальных языках ничего нового по сравнению с машиной Тьюринга не приносит. И обычный компьютер с потенциально бесконечной памятью эквивалентен машине Тьюринга. А если в языках программирования типа Си запретить циклы кроме for и goto, то разрешённые программы будут вычислять в точности примитивно рекурсивные функции.

Последнее утверждение мне всегда казалось очевидным. Но я вот тут задумался, насколько оно очевидно... И захотелось почитать мнения разных уважаемых участников форума по этому поводу.

-- Сб июл 21, 2012 23:40:58 --

bin в сообщении #597603 писал(а):

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

Да, это, собственно, то, что я имел в виду. Рад, что Вики со мной согласна. Хотя в Вики иногда встречается чепуха, так что это, увы, не авторитет...

А вот интересно, насколько строго можно доказать процитированный тезис? Ну, то есть я верю, что можно очень строго, но насколько большим и сложным окажется доказательство?

[bin]

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

Да, это, собственно, то, что я имел в виду. Рад, что Вики со мной согласна. Хотя в Вики иногда встречается чепуха, так что это, увы, не авторитет...

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

-- Сб июл 21, 2012 21:25:02 --

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

А вот интересно, насколько строго можно доказать процитированный тезис? Ну, то есть я верю, что можно очень строго, но насколько большим и сложным окажется доказательство?

К сожалению, в этом помочь не смогу Sorry.

[Lukin]

Работая со строками, используем Куайн-программу (реализуемую на одних for циклах) в качестве рекурсивного оператора ничем не ограниченного по числу циклов.
Текст программы выглядит пристойно - удовлетворяет Вашим требованиям, (никаких repeat, while, goto, одни for), а вот ее работа выходит за рамки примитивной рекурсии. Интуиция подсказывает.
Или я не прав ?