Обсуждение:Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть — различия между версиями
Juliet (обсуждение | вклад) |
Slavav (обсуждение | вклад) (→Ошибка в статье: Новая тема) |
||
| Строка 2: | Строка 2: | ||
Хорошо, я не против — [[Участник:Juliet|Juliet]] 22:30, 22 марта 2009 (MSK) | Хорошо, я не против — [[Участник:Juliet|Juliet]] 22:30, 22 марта 2009 (MSK) | ||
| + | |||
| + | == Ошибка в статье == | ||
| + | |||
| + | Добрый день! | ||
| + | |||
| + | В статье утверждается, что существуют рекурсивные функции, которые нельзя вычислить итеративно. В качестве примера приводится функция Аккермана. Это утверждение ложно. | ||
| + | Функцию Аккермана, как и любую другую рекурсивную функцию можно вычислить итеративно. | ||
| + | |||
| + | Функция Аккермана общерекурсивна, следовательно, она частичнорекурсивна. Класс частичнорекурсивных функций совпадает с классом машин Тьюринга. Любая машина Тьюринга может быть вычислена итеративно (ее семантика определяется итеративно). | ||
| + | |||
| + | С уважением, | ||
| + | Станислав Володарский | ||
Текущая версия на 16:39, 21 мая 2009
Я не настаиваю, но вообще отметка категории обычно внизу ставится: в Википедии, по крайней мере, по моему опыту, обычно так. Видимо, из тех соображений, что соответствующий элемент страницы отображается всегда внизу. — Ulysses 21:44, 22 марта 2009 (MSK)
Хорошо, я не против — Juliet 22:30, 22 марта 2009 (MSK)
Ошибка в статье
Добрый день!
В статье утверждается, что существуют рекурсивные функции, которые нельзя вычислить итеративно. В качестве примера приводится функция Аккермана. Это утверждение ложно. Функцию Аккермана, как и любую другую рекурсивную функцию можно вычислить итеративно.
Функция Аккермана общерекурсивна, следовательно, она частичнорекурсивна. Класс частичнорекурсивных функций совпадает с классом машин Тьюринга. Любая машина Тьюринга может быть вычислена итеративно (ее семантика определяется итеративно).
С уважением, Станислав Володарский
