Какой-либо язык может потенциально использоваться для создания какой-либо программы?

Это вопрос времени, не так ли? Отсутствие подходящих библиотек и API для BASIC может заставить Adobe Проект Photoshop длился вечно, и по завершении он может работать не очень гладко, но теоретически выполнимый.

Вы также можете воссоздать Windows 95, вводя бит за битом в шестнадцатеричный редактор, но какой в ​​этом смысл?

Вы должны быть осторожны с тем, что Вы имеете в виду под "любой программой". Например, если вас попросили написать программу, которая создает на диске текстовый файл, содержащий "Hello world", и вас попросили написать его на чистом Javascript, это было бы невозможно, потому что чистый Javascript не имеет возможности записывать что-либо на диск. .

Для подробного обсуждения этой идеи вы можете прочитать о вычислимости .

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

Конечно (вроде). Есть компромисс, производительность. Кроме того, некоторые языки могут не иметь доступа к определенным функциям системы, что делает их неспособными выполнять определенные задачи на машине. Некоторые языки просто ... слабее других, и на это потребуется время.

Это зависит от того, как именно вы определяете «любую программу» и «любой язык».

Начнем с первого: «любая программа». Есть много программ (на самом деле существует бесконечно много программ), которые вообще невозможно написать , независимо от языка программирования. Одной из самых известных является так называемая проблема остановки: напишите программу H , которая при задании любой программы P и любого ввода x определяет, будет ли P (x) в конечном итоге остановится. Алан Тьюринг доказал много десятилетий назад, что существование такой программы невозможно . Следовательно, вы не можете написать эту программу на любом языке программирования.

Теперь поговорим о «любом языке». На самом деле существуют разные классы языков. Некоторые из них более могущественны, чем другие. Например, регулярные выражения (которые являются своего рода языком программирования) не могут , но вычислять любую произвольную функцию. Их вычислительная мощность ограничена. Однако большинство языков программирования общего назначения обычно называют «полными по Тьюрингу».

Краткая история: чтобы доказать неразрешимость проблемы остановки, Алан Тьюринг изобрел гипотетическую машину, названную машиной Тьюринга. TM - это, по сути, гипотетический компьютер с бесконечной памятью, который вычисляет определенную функцию. Оказывается, вы можете построить универсальную машину Тьюринга, которая может эмулировать любую другую машину Тьюринга.

Примерно в то же время Алонсо Черч изобрел лямбда-исчисление.LC - это также абстрактная математическая модель вычислений, но полностью другая. Люди начали задаваться вопросом: какая из этих двух моделей более мощная? Есть ли что-нибудь, что UTM может вычислить, что LC не может, и наоборот? Может ли LC решить проблему остановки?

Как оказалось, вы можете написать эмулятор для UTM на LC и создать TM, который интерпретирует LC. Это означает, что TM может вычислить все, что может вычислить LC (просто запустив его в интерпретаторе), а LC может вычислить все, что может вычислить UTM (просто запустив его в эмуляторе). Итак, у нас есть

LC ≤ UTM ∧ UTM ≤ LC ⇒ LC = UTM

По-английски: LC и UTM одинаково эффективны. Фактически, оказывается, что каждая модель вычислений и каждая машина и каждый язык программирования, который мы когда-либо находили, самое большее как мощный как LC и UTM, да и все остальные модели. Это приводит к так называемому тезису Чёрча-Тьюринга , в котором утверждается, что все достаточно мощные модели вычислений одинаково мощны, и не может быть модели вычислений более мощной, чем UTM или LC. (Могут быть модели вычислений, которые менее мощные, такие как, например, регулярные выражения, полные функции или язык только с ограниченными циклами.)

Мы называем такие модели вычислений полными по Тьюрингу. . И, кстати, вам не нужно много, чтобы быть полным по Тьюрингу .

Итак, разобравшись с этим, мы можем теперь определить, что мы подразумеваем под «любой программой» и «любым языком»:

Если программа может быть написана на одном полном по Тьюрингу языке ], то его можно записать на любом полном по Тьюрингу языке .

Думаю, если в вашем языке есть средства для доступа ко всему необходимому вводу и выводу, тогда да.

Если вы добавили «... на достаточно мощном компьютере и с учетом того, что в языке есть библиотеки, которые могут обрабатывать все, что нужно программе», тогда ответ все равно будет отрицательным. Некоторые языки могут сводить программистов с ума до такой степени, что они убивают себя. Если бы мне когда-либо пришлось вернуться к Visual Basic 3 (без классов или коллекций), я бы не знал, как переписать Блокнот.

Я думаю, что если вы добавите "достаточно творческий" и включите эксплуатацию в число программирования, а определение "любая программа" - это любая программа, которая уже существует, то ответ будет положительным.