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

[Esp_]

alexBlack писал(а):

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

Заведомо большее, чем что?

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

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

alexBlack в сообщении #597970 писал(а):

А если смоделировать while взяв заведомо бОльшее количество итераций ?

А как Вы оцените сверху нужное количество итераций?

Теоретически никак. Есть вычислимые функции, любая оценка времени вычисления которых не примитивно рекурсивна. Увы

Более того, вычислимая функция примитивно рекурсивна тогда и только тогда, когда время её вычисления оценивается сверху примитивно рекурсивной функцией!

-- Вс июл 22, 2012 21:19:14 --

(Оффтоп)

alexBlack в сообщении #597970 писал(а):

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

Предлагаю игнорировать пользователя Lukin. Лично мне очевидно, что он не разбирается в теме и гонит пургу. Надеюсь, Вам тоже это очевидно

[Lukin]

(Оффтоп)

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

Предлагаю игнорировать пользователя Lukin. Лично мне очевидно, что он не разбирается в теме и гонит пургу. Надеюсь, Вам тоже это очевидно

Поддерживаю, ибо имеется монополия на "бесконечность", в которую пользователь Lukin не вписывается, а, что такое монополия, можно ознакомится, в экономическом разделе.
На всякий случай в очередной раз приведу ссылку, на более мужественных умов:
П.Вопенка " Математика в альтернативной теории множеств"
Профессора Снейп(а), прошу не беспокоится, ибо любая монополия имеет свойство заканчиваться.

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

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

Пусть существует конечная программа , с вложенными циклами, тогда количество итераций такой программы вычисляется примитивно рекурсивной функцией .

Думаю, да, это так. Вопрос в том, насколько строго это можно доказать.

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

Существует частично рекурсивная функция , которая начиная с некоторого своего аргумента для любых оставшихся аргументов аргументов принимает значение 0 только если .

А вот этого я просто не понимаю. Подредактируйте, пожалуйста.

Впрочем, неважно. Из существования $f_1$ выводится примитивная рекурсивность функции, вычисляемой программой. Это просто. Функция $\varphi_P(x,t)$, дающая результат вычисленгий при входе $x$ после $t$ шагов работы программы, примитивно рекурсивна. Поскольку время вычислений ограничивается прф, достаточно применить ограниченную минимизацию.

[Esp_]

Цитата:

Думаю, да, это так. Вопрос в том, насколько строго это можно доказать.

Это легко доказывается индукцией по сложности программы.
Базис индукции - программа с одним циклом.

Цитата:

А вот этого я просто не понимаю. Подредактируйте, пожалуйста.

А здесь на самом деле получается доказать то, что сказали вы:

Цитата:

Более того, вычислимая функция примитивно рекурсивна тогда и только тогда, когда время её вычисления оценивается сверху примитивно рекурсивной функцией!

там как раз и получается, что время на вычисление функции получается больше.

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

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

Это легко доказывается индукцией по сложности программы.
Базис индукции - программа с одним циклом.

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

[_hum_]

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

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

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

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

Тогда нужно еще и возможность определять процедуры/функции запрещать, потому как с их помощью можно реализовать циклы с зависящим от исходных данных программы количеством итераций (просто организовав взаимные вызовы).

А вообще, если убрать возможность реализации циклов с зависимым от исходных данных количеством итераций, то все программы на таком языке будут равносильны блок-схемам "без циклов", или более точно, построенным в соответствие с принципами структурного программирования, но использующим только структуру следования и ветвления (без структуры повторения). Почему этого недостаточно для задания любой примитивно-рекурсивной функции, скорее всего доказывается так же, как и то, почему из определения примитивно-рекурсивных функций нельзя убрать операцию рекурсии, не сузив при этом класс примитивно-рекурсивных функций.

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

_hum_ в сообщении #599064 писал(а):

А вообще, если убрать возможность реализации циклов с зависимым от исходных данных количеством итераций...

Это совсем маленький класс функций получится. Всё зависит от того, какие базовые операции Вы допускаете. Сложение, умножение... что ещё? Если только это, то Вы даже возведение в степень не определите.

Я там где-то писал в одном из следующих постов уточнение условия. Рекурсия запрещена, как явная, так и неявная. Неявная - это то, что Вы описали. Другими словами, ориентированный граф с вершинами-процедурами и рёбрами, соединяющими процедуры $A$ и $B$, когда из $A$ можно вызвать $B$, должен быть деревом. То есть не иметь циклов.

[_hum_]

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

Цитата:

_hum_ в сообщении #599064 писал(а):
А вообще, если убрать возможность реализации циклов с зависимым от исходных данных количеством итераций...

Это совсем маленький класс функций получится.

Не совсем понял это замечание. Хотите сказать, что это ограничение слишком сильное? Но ведь все вводимые вами ранее ограничения (на отсутствие рекурсии (прямой и косвенной), циклов с динамическими условиями выхода) в конце-концов сводятся именно к этому требованию (если речь идет о языках типа Паскаля) - такую программу можно написать на основе пакетирования лишь одних структур следования и ветвления (без задействования структуры повторения).

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

Всё зависит от того, какие базовые операции Вы допускаете.

Не я, а вы как топик-стартер :)
Я так подозреваю, при постановке проблемы под языком вы имели в ввиду популярные в студенческой среде Паскаль и Си. Тогда можно их и придерживаться (допускать стандартные в этих языках операции и функции).

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

Сложение, умножение... что ещё? Если только это, то Вы даже возведение в степень не определите.

Кстати, как это строго доказать? Я вот как-то так с наскоку и не смог :(

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

_hum_ в сообщении #599275 писал(а):

Но ведь все вводимые вами ранее ограничения (на отсутствие рекурсии (прямой и косвенной), циклов с динамическими условиями выхода) в конце-концов сводятся именно к этому требованию (если речь идет о языках типа Паскаля) - такую программу можно написать на основе пакетирования лишь одних структур следования и ветвления (без задействования структуры повторения).

Это неверно.

Вот давайте пример. Функция берёт на входе два натуральных числа и возвращает их произведение. Операция умножения запрещена, есть только $+$.

Код очевиден:

function mult(x,y: integer):integer;
var i,m: integer;
begin
  m := 0;
  for i := 1 to x do m := m + y;
  return m
end;

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

-- Чт июл 26, 2012 00:34:47 --

_hum_ в сообщении #599275 писал(а):

Кстати, как это строго доказать? Я вот как-то так с наскоку и не смог :(

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

[_hum_]

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

Это неверно.

Вот давайте пример. Функция берёт на входе два натуральных числа и возвращает их произведение. Операция умножения запрещена, есть только $+$.

Код очевиден:

Мы друг друга наверное недопонимаем. Я утверждаю, что все приводимые вами раньше ограничения равносильны одному-единственному требованию - программа должна писаться совсем без циклов. Чтобы говорить, что это неверно, нужно как минимум привести пример программы, которая удовлетворяет вашим ограничениям (не использовать рекурсии, не использовать циклы с динамическим условием) и в то же время не может быть написана без циклов. Ваш пример под нее не подходит (в нем используется цикл с числом итераций, зависящим от исходного данного $x$).

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

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

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

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

_hum_ в сообщении #599368 писал(а):

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

В смысле? Это Вы утверждаете, что без циклов. Я такого не утверждал. А утверждал обратное: без циклов невозможно. Вот Вам программа с циклом: перепишите её без цикла.

_hum_ в сообщении #599368 писал(а):

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

Хотя бы просто потому, что длина результата экспоненциально зависит от длины входа. Только на то, чтобы записать результат вычислений, Вам понадобится экспоненциальное время.

_hum_ в сообщении #599368 писал(а):

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

Здесь Вы ошибаетесь. В теории вычислимости очень популярны пошаговые конструкции; собственно, она почти вся из этого состоит.

Вычисления производятся не мгновенно, а за конечное время. Просто до теории сложности мы не интересуемся конкретными оценками времени вычислений: конечное - ну и ладно, остальное не важно.

_hum_ в сообщении #599368 писал(а):

очень уж некрасиво выглядит притягивание теории сложности

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

-- Чт июл 26, 2012 01:08:19 --

Вам что надо: шашечки или ехать?

[_hum_]

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

В смысле? Это Вы утверждаете, что без циклов. Я такого не утверждал. А утверждал обратное: без циклов невозможно. Вот Вам программа с циклом: перепишите её без цикла.

:)
Еще раз - исходная постановка вашей проблемы (с моей точки зрения) выглядит так:
если договориться не использовать в написании программы на языке программирования наподобие Паскаль
1) рекурсивных функций (функций, в определении которых есть вызовы самих себя);
2) косвенных вызовов функции самой себя через вызовы промежуточных (косвенная рекурсия);
3) циклов while, for, until с динамическим условием завершения (условием завершения, зависящим от исходных данных программы);
4) оператора безусловного перехода goto,
то останется ли возможность реализовать любую примитивно-рекурсивную функцию?
Я правильно понял? Если да, то я утверждаю, что ваша проблема равносильна следующей:
если договориться при написании программы на Паскале использовать только пакетирование структур следования и ветвления, то останется ли возможность реализовать любую примитивно-рекурсивную функцию?

Только и всего.

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

Хотя бы просто потому, что длина результата экспоненциально зависит от длины входа. Только на то, чтобы записать результат вычислений, Вам понадобится экспоненциальное время.

Это не очевидно, поскольку мы работаем не с машиной Тьюринга, а с неким исполнителем, у которого операции ввода/вывода, вообще говоря, могут быть атомарными. И если уж строго, то надо тогда оговаривать подробно этого исполнителя и проводить оценки.

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

Здесь Вы ошибаетесь.

Я имел в виду, что ядро теории алгоритмов, насколько я имею представление, рассматривает свойства алгоритмов, определенных с точностью до эффективного изоморфизма. А потому в ней не имеет смысла говорить о времени исполнения, поскольку оно не выдерживает этого изоморфизма (один и тот же алгоритм может в одном представлении иметь одну сложность, а в другом другую).
Вопрос, который вы поставили, напоминает общий вопрос - почему при определении вычислимых функций нельзя отказаться от операции рекурсии в декларативных моделях вычисления и от циклов в императивных. И хотелось бы дать на него ответ в рамках этой теории.

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

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

Индукцию для доказательства какого утверждения?

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

_hum_ в сообщении #599390 писал(а):

Я правильно понял?

Нет.

_hum_ в сообщении #599390 писал(а):

3) циклов while, for, until

while и until нельзя, for можно. При использовании for нельзя переменную цикла и границы цикла менять внутри самого цикла.

-- Чт июл 26, 2012 10:17:01 --

_hum_ в сообщении #599390 писал(а):

Я имел в виду, что ядро теории алгоритмов, насколько я имею представление, рассматривает свойства алгоритмов, определенных с точностью до эффективного изоморфизма. А потому в ней не имеет смысла говорить о времени исполнения, поскольку оно не выдерживает этого изоморфизма (один и тот же алгоритм может в одном представлении иметь одну сложность, а в другом другую).

Где это Вы такой чепухи нахватались?

-- Чт июл 26, 2012 10:17:52 --

_hum_ в сообщении #599390 писал(а):

Индукцию для доказательства какого утверждения?

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

[_hum_]

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

_hum_ в сообщении #599390 писал(а):

Я правильно понял?

Нет.

И? Что именно неправильно?

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

_hum_ в сообщении #599390 писал(а):

3) циклов while, for, until

while и until нельзя, for можно. При использовании for нельзя переменную цикла и границы цикла менять внутри самого цикла.

Ну, и чем это отличается от моего

_hum_ в сообщении #599390 писал(а):

3) циклов while, for, until с динамическим условием завершения (условием завершения, зависящим от исходных данных программы);

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

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

_hum_ в сообщении #599390 писал(а):

Я имел в виду, что ядро теории алгоритмов, насколько я имею представление, рассматривает свойства алгоритмов, определенных с точностью до эффективного изоморфизма. А потому в ней не имеет смысла говорить о времени исполнения, поскольку оно не выдерживает этого изоморфизма (один и тот же алгоритм может в одном представлении иметь одну сложность, а в другом другую).

Где это Вы такой чепухи нахватались?

Вообще, мне кажется, не совсем корректно высказываться подобным образом без всякой аргументации. Что чепуха? Что ядро теории алгоритмов не заботится о времени исполнения, или что вычислительная сложность алгоритма зависит от модели вычислений, в которой он реализуется?
Читаем хотя бы Wiki: Theory of computation.

Цитата:

In theoretical computer science and mathematics, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory, computability theory and computational complexity theory.

Рисунок: http://en.wikipedia.org/wiki/File:Theoretical_computer_science.svg

Цитата:

Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer.

Цитата:

Complexity theory considers not only whether a problem can be solved at all on a computer, but also how efficiently the problem can be solved.

Так вот в моем высказывании под "ядром теории алгоритмов" я понимал раздел Computability theory.

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

_hum_ в сообщении #599390 писал(а):

Индукцию для доказательства какого утверждения?

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

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