Это зависит от того, как именно вы определяете «любую программу» и «любой язык».
Начнем с первого: «любая программа». Существует много программ (на самом деле, существует бесконечно много программ), которые не могут быть написаны вообще , независимо от языка программирования. Одной из самых известных является так называемая проблема остановки: напишите программу H, которая при задании любой программы P и любого ввода x определяет, остановится ли P(x) в конечном итоге. Алан Тьюринг доказал много десятилетий назад, что такая программа существует невозможно . Ergo, вы не можете написать эту программу на любом языке программирования.
Теперь поговорим о «любом языке». Есть на самом деле разные классы языков. Некоторые из них более могущественны, чем другие. Например, регулярные выражения (которые являются разновидностью языка программирования) могут не вычислять любую произвольную функцию. Они ограничены в своих вычислительных возможностях. Однако большинство языков программирования общего назначения обычно называют «полными по Тьюрингу».
Краткая история: чтобы доказать неразрешимость проблемы остановки, Алан Тьюринг изобрел гипотетическую машину под названием Машина Тьюринга. ТМ - это в основном гипотетический компьютер с бесконечной памятью, который вычисляет определенную функцию. Оказывается, вы можете построить универсальную машину Тьюринга, которая может эмулировать любую другую машину Тьюринга.
Примерно в то же время Алонзо Черч изобрел лямбда-исчисление. LC является также абстрактной математической моделью вычисления, но полностью отличается. Люди начали задаваться вопросом: какая из этих двух моделей более мощная? Есть ли что-нибудь, что UTM может вычислить, что LC не может, и наоборот? Может ли ЛК решить проблему остановки?
Как оказалось, вы можете написать эмулятор для UTM в LC и вы можете создать TM, который интерпретирует LC. Это означает, что TM может вычислить все, что может вычислить LC (просто запустив его в интерпретаторе), а LC может вычислить все, что может вычислить UTM (просто запустив его в эмуляторе). Итак, у нас есть
LC ≤ UTM ∧ UTM ≤ LC ⇒ LC = UTM
На английском языке: LC и UTM одинаково мощны. Фактически, оказывается, что каждая модель вычислений и каждая машина и каждый язык программирования, который мы когда-либо находили, максимум как мощный как LC и UTM и действительно любая другая модель. Это приводит к так называемому тезису Черча-Тьюринга , в котором говорится, что все достаточно мощные модели вычислений одинаково мощны, и не может быть модели вычислений, более мощной, чем UTM или LC. (Могут быть модели вычислений, которые являются менее мощными, как, например, регулярные выражения или полные функции или язык только с ограниченными циклами.)
Мы называем такие модели вычислений Тьюринг-полными . И, кстати, вам не нужно много, чтобы быть полным по Тьюрингу .
Итак, теперь мы можем определить, что мы подразумеваем под «любой программой» и «любым языком»:
Если программа может быть написана на одном языке, полном по Тьюрингу , то она может быть написана на любом языке, полном по Тьюрингу .