Обсуждение:Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть

Я не настаиваю, но вообще отметка категории обычно внизу ставится: в Википедии, по крайней мере, по моему опыту, обычно так. Видимо, из тех соображений, что соответствующий элемент страницы отображается всегда внизу. — Ulysses 21:44, 22 марта 2009 (MSK)

Хорошо, я не против — Juliet 22:30, 22 марта 2009 (MSK)

Ошибка в статье

Добрый день!

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

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

С уважением, Станислав Володарский