Кратко: по мощности (что вычислимо) машины Тьюринга и лямбда‑исчисление эквивалентны (одно и то же множество вычислимых функций); практически же они очень разные по модели, представлению данных, стоимости шагов и удобству оптимизаций.
Основное равенство
- Формально: множество функций $\{f:\mathbb{N}\to \mathbb{N}\mid f\text{вычислима на ТМ}\}$ совпадает с множеством функций, определимых в $\lambda$-исчислении. Это — версия тезиса Чёрча—Тьюринга.
- Лямбда‑конструкция: абстрактно $\lambda x.M$, редукция $\beta$-редукция $(\lambda x.M)N\to M[x:=N]$.
Ключевые различия (практическая сторона)
- Модель вычислений:
- Тьюринговая машина: императивный, низкоуровневый, явное состояние, лента/память, пошаговые перемещения и записи — удобна для анализа времени/памяти в терминах машинных шагов.
- $\lambda$-исчисление: функциональная, выражения/редукции, функции как значения, заменяющие вычисления подстановкой/редукцией — удобна для семантики, трансформаций и доказательства корректности оптимизаций.
- Представление данных:
- На ТМ можно работать с эффективными кодировками (бинарные числа, слова).
- В чистом $\lambda$-исчислении попытки кодировать числа/списки чистыми функциями (Church‑числа) обычно очень неэффективны: напр., $\overline{n}=\lambda f.\lambda x.f^{(n)}x$ — дорогие арифметические операции.
- Стоимость шага/модель затрат:
- На ТМ один базовый шаг простой и одинаковой стоимости.
- В $\lambda$-исчислении одна $\beta$-редукция может требовать большой работы (подстановка больших термов). Разные стратегии (call‑by‑value, call‑by‑name, call‑by‑need) дают разные временные характеристики. Нужно учитывать модель затрат (например, графовые редукции с шэарингом, чтобы избежать экспоненциального копирования).
- Компиляция и реализация:
- Функциональные языки (на базе $\lambda$) реализуют высокоуровневые механизмы: замыкания, аллокейшн, сборка мусора, CPS/ламбда‑лифтинг; это даёт удобные оптимизации (инлайнинг, константная пропагация, deforestation), но имеет накладные расходы.
- Императивные модели ближе к машинному коду, дают прямые оптимизации (регистровое распределение, разворачивание циклов, кеш‑оптимизация).
- Оптимизации и преобразования:
- В $\lambda$-мире: эквивалентностные преобразования на основе редукций ($\beta$, $\eta$), CPS, анализ замыканий, ленивые вычисления, общие алгоритмы оптимизации на уровне выражений.
- В императивной/ТМ-модели: локальные трансформации потока управления, аллокейшн памяти, инструкции низкого уровня.
- Сложностная инвариантность:
- Для «разумных» моделей вычислений часто соблюдается инвариантность классов сложности (полиномиальные и полиномиальные по памяти классы устойчивы), т.е. симуляция между моделями даёт не более полиномиального оверхеда. Но константные и логарифмические факторы, а также точная стоимость операций могут сильно отличаться на практике.
Практические рекомендации для языка и оптимизации
- Для дизайна высокоуровневого функционального языка лучше опираться на $\lambda$-модель (семантика, трансформации, эквивалентности). Но при реализации учитывать накладные расходы: использовать графовые представления (sharing), закрытия, сборщик мусора, CPS/ANF для эффективной генерации кода.
- Для низкоуровневой эффективности и точного анализа времени/памяти опираться на машинную модель (регистры, память, кеш), т.е. компилировать функциональные конструкции в эффективный машинный код.
- При оптимизации помнить: некоторые эквивалентные по семантике преобразования могут ухудшать производительность (например, неаккуратная инлайнинг‑стратегия увеличит копирование данных), поэтому анализ затрат и модель выполнения критичны.
Итого: эквивалентность по вычислимости — да; практически $\lambda$-исчисление удобнее для семантики и трансформаций, машины Тьюринга (и императивная модель) — для точного анализа и низкоуровневой оптимизации. Реальные компиляторы связывают обе модели: используют $\lambda$-набор трансформаций на входе и мэппят их на эффективную машинную модель в конце.