Теория автоматов и функциональное программирование

Question

Недавно я начал изучать функциональное программирование и получить доступ к Haskell. С фундаментальным различием между функциональной парадигмой и другими является то, что мы не поддерживаем состояния, и нет никаких вычислений, как в императивной парадигме. Основной теорией императивного программирования является теория автоматов и теория автоматов, которая является основой для компьютеров.

Таким образом, я не вижу никакого отношения между теорией автоматов и функциональным программированием. Так что функциональное программирование изменило основы программирования наизнанку?

Answer 1

Примерно в то же время, как Тьюринга машин, где развитом (я только предполагаю, что вы имеете в виду ДЧ, когда вы говорите, теория автоматов является основой для компьютеров) и лямбда-исчисление было предложено в качестве модели вычисление (хорошо не совсем компьютеров, но близко). Оба понятия оказались эквивалентными в том смысле, что все, что может быть «реализовано» на ТМ, также может быть «реализовано» с помощью лямбда-термина и наоборот. Более того, функциональное программирование является более или менее реализацией (типизированного) лямбда-исчисления. Поэтому я думаю, что это всего лишь два разных способа взглянуть на одно и то же.