Re[2]: kylix 2
Здравствуйте!
В пятницу, 10-го января 2003, в 13:41:17 по московскому времени
(пятница, 12:41 (GMT +0200) на часах автора исходного письма)
Dmitry Astapov написал:
DA> Как следует из пока что не опровергнутого тезиса Черча, ассемблер,
DA> С, Haskell и все остальные языки програмирования одинаковы в
DA> смысле мощности множества задач, которые можно решить с их
DA> помощью.
Нет, тезис Чёрча для этого не нужен. То, что все эти языки
функционально эквивалентны, т.е. все возможные программы на них
вычисляют один и тот же класс функций -- математическая теорема.
Строго доказанная. Совпадает этот класс также и с классом функций,
вычисляемых машинами Тьюринга, и с классом частично-рекурсивных
функций, и с ещё несколькими классами. Это не тезис, а теорема. Тезис
же Тьюринга-Чёрча утверждает, что этот класс совпадает также с классом
эффективно вычислимых функций или функций, вычислимых алгоритмически.
Этот тезис действительно нельзя формально ни доказать, ни опровергнуть
(хотя неформально опровергнуть его можно, а неформально доказанным он
считается в данный момент), поскольку он включает в себя
неопределяемое понятие эффективно вычислимой функции. Поэтому на
данный момент именно этот тезис используется как определение функции,
вычислимой алгоритмически.
Есть, правда, ещё расширенный тезис Тьюринга-Чёрча. Он утверждает,
что все возможные функционально полные машины и языки
программирования, удовлетворяющие разумным ограничениям, реализуются
друг другом с не более, чем полиномиальным увеличением времени. Этот
тезис тоже недоказуем, поскольку содержит понятие "разумных
ограничений", опять-таки не формализуемое. Например, этим разумным
ограничениям не удовлетворяют недетерминированные машины. Однако для
конкретных примеров языков программирования этот тезис доказан,
поэтому в этих случаях является теоремой.
И ещё один момент:
DA> ассемблер, С, Haskell и все остальные языки програмирования
Немного неаккуратное высказывание. Например, SQL не является
функционально полным языком, хотя точно класс вычисляемых им функций
ещё никто не описал. Так что не "все остальные языки
программирования", а "все остальные универсальные языки
программирования".
Интересно, а какое отношение всё это имеет к теме потока?
--
С уважением,
Руслан Батдалов
Подполковником быть хорошо, а под генералом лучше
Reply to: