On different programming languages ...
Evening, Ruslan.
Ruslan Batdalov <linnando@tolkien.ru> 19:26 10/1/2003 wrote:
DA>> Как следует из пока что не опровергнутого тезиса Черча, ассемблер,
DA>> С, Haskell и все остальные языки програмирования одинаковы в
DA>> смысле мощности множества задач, которые можно решить с их
DA>> помощью.
RB> Нет, тезис Чёрча для этого не нужен. То, что все эти языки
RB> функционально эквивалентны, т.е. все возможные программы на них
RB> вычисляют один и тот же класс функций -- математическая теорема.
RB> Строго доказанная. Совпадает этот класс также и с классом функций,
[skip]
Спасибо за напоминание :)
Да, давно я не брал в руки старых конспектов ...
RB> Есть, правда, ещё расширенный тезис Тьюринга-Чёрча. Он утверждает,
RB> что все возможные функционально полные машины и языки
RB> программирования, удовлетворяющие разумным ограничениям, реализуются
RB> друг другом с не более, чем полиномиальным увеличением времени. Этот
RB> тезис тоже недоказуем, поскольку содержит понятие "разумных
RB> ограничений", опять-таки не формализуемое. Например, этим разумным
RB> ограничениям не удовлетворяют недетерминированные машины. Однако для
RB> конкретных примеров языков программирования этот тезис доказан,
RB> поэтому в этих случаях является теоремой.
RB> И ещё один момент:
DA>> ассемблер, С, Haskell и все остальные языки програмирования
RB> Немного неаккуратное высказывание. Например, SQL не является
RB> функционально полным языком, хотя точно класс вычисляемых им функций
RB> ещё никто не описал. Так что не "все остальные языки
RB> программирования", а "все остальные универсальные языки
RB> программирования".
RB> Интересно, а какое отношение всё это имеет к теме потока?
А никакого :)
--
Dmitry Astapov //ADEpt E-mail: adept@umc.com.ua
GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498 2B08 7867 4860 F5D7 639D
Reply to: