Evening, Ruslan. Ruslan Batdalov <[EMAIL PROTECTED]> 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: [EMAIL PROTECTED] GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498 2B08 7867 4860 F5D7 639D
