Почему некоторые языки программирования Тьюринга завершены, но не обладают некоторыми возможностями других языков?

42

Я столкнулся со странной проблемой при написании интерпретатора, который (должен) подключаться к внешним программам / функциям: функции в «C» и «C ++» не могут перехватывать переменные функции , например, я не могу создать функцию, которая вызывает «printf» с точно такими же аргументами, которые он получил, и вместо этого должен вызвать альтернативную версию, которая принимает объект с переменным числом аргументов. Это очень проблематично, так как я хочу иметь возможность создавать объект, который содержит анонимный хук.

Итак, я подумал, что это странно, поскольку Forth , JavaScript и, возможно, множество других языков могут сделать это очень легко, не прибегая к ассемблеру / машинному коду. Поскольку другие языки могут сделать это так легко, означает ли это, что класс задач, которые может решить каждый язык программирования, в действительности зависит от языка, даже если все эти языки полны по Тьюрингу ?

Мистер Минти Фреш
источник
33
Вы должны посмотреть на тьюринг тьюринга . Это увлекательный тип языка программирования, в котором преднамеренно доступно как можно меньше операций, и при этом он все еще завершен. Большинству из них не хватает базовых типов данных, функций, даже таких простых вещей, как объявление переменных. Лично я считаю, что кодирование в них - это очень весело, так как это вынуждает вас покинуть свою зону комфорта, чтобы попробовать что-то излишне сложное.
DJMcMayhem
8
Посмотрите на то, что делает машина Тьюринга, и вы увидите, что «полный Тьюринг» - это очень небольшое препятствие для прояснения. В основном все, что может «читать», «писать» и «прыгать», поддерживая базовую арифметику, является полным по Тьюрингу. Это намного ниже уровня языковых возможностей, на которые вы смотрите.
30.09.16
2
Чтобы быть еще более смешным: инструкция MOV на процессоре x86 является полной по Тьюрингу. См. Cl.cam.ac.uk/~sd601/papers/mov.pdf для деталей.
Гарет МакКоган,
3
Даже карточная игра Magic: The Gathering завершена по Тьюрингу. Полнота по Тьюрингу не имеет ничего общего с особенностями языка.
Мачта
2
Кстати, есть и очень сложные языки программирования, которые еще не завершены, такие как те, что проверяют.
盛安安

Ответы:

68

Полные языки Тьюринга могут вычислять один и тот же набор функций , который представляет собой набор общих рекурсивных частичных функций. Вот и все.NkN

Это ничего не говорит о языковых особенностях. Машина Тьюринга имеет очень ограниченные композиционные особенности. Нетипизированный -calculus гораздо более композиционный, но в нем отсутствуют многие функции, обычно встречающиеся в современных языках.λ

Полнота Тьюринга ничего не говорит о наличии типов, встроенных массивах / целых числах / словарях, возможностях ввода / вывода, доступа к сети, многопоточности, динамического распределения, ...

Просто потому, что в Java нет функции X (скажем, макросов, типов более высокого ранга или зависимых типов), она не перестает быть завершенной по Тьюрингу.

Полнота и языковая выразительность Тьюринга - это два разных понятия.

чи
источник
43
Эдвин Брэди, дизайнер Idris, (только половина) в шутку использует (я не знаю, изобрел ли он его) термин «Tetris-complete», чтобы выразить эту разницу между «может вычислять любую вычислимую функцию на натуральных числах» и «может использоваться для написания нетривиальных программ, взаимодействующих со средой ".
Йорг Миттаг,
12
Вы также можете упомянуть, что у вас могут быть такие вещи в C / C ++. Вам просто нужно написать некоторый код, который действует как компилятор на C / C ++ для другого языка, в котором они есть, где ваш код компилирует строку в вашем коде на C / C ++. Тогда вы можете просто программировать что-то вроде Java в вашем C-файле. Это все было бы много работы, но это возможно (доказуемо, потому что C / C ++ завершен по Тьюрингу).
Shufflepants
4
@Shufflepants Мне интересно, однако, действительно ли полезно говорить «я могу сделать это на C ++, поскольку могу интерпретировать другой язык». Таким образом, Java, ML, C ++ эквивалентны. TM с оракулом для системных вызовов (I / O) также эквивалентны. Боюсь, что по этим причинам практически все языки одинаково выразительны. Если это так, сравнивать языки бесполезно.
Чи
9
@chi Вы правы, они эквивалентны. Вот что значит быть завершенным по Тьюрингу. Все, что можно сделать с одной системой Turing Complete, можно сделать с другой системой Turing Complete. Это может быть не удобно делать в конкретной системе. А удобство выполнения разных вещей - это основной способ сравнения разных языков программирования. Но вопрос не в этом.
Shufflepants
5
@Rhymoid Если C не завершен по Тьюрингу по причинам, связанным с доступом к памяти, или из-за того, что возможность посылки произвольных сигналов на подключенное устройство с произвольно большим объемом памяти не учитывается, то можно утверждать, что ни один язык или устройство реального мира не является Тьюринговым завершенным. , Но я не чувствую, что это очень продуктивная линия рассуждений.
Шафлпантс,
47

Полнота по Тьюрингу - это абстрактное понятие вычислимости. Если язык является полным по Тьюрингу, то он способен выполнять любые вычисления, которые может выполнять любой другой полный по Тьюрингу язык.

Это, однако, не говорит о том, насколько это удобно. Некоторые функции, которые просты в некоторых языках, могут быть очень трудными в других из-за выбора дизайна. Полнота Тьюринга просто говорит о том, что вы можете делать вычисления. В качестве крайнего примера, может быть трудно перехватить varadic функции в C ++, но можно написать интерпретатор JavaScript в C ++, который может перехватывать функции variadic.

Языковой дизайн - довольно интересное искусство. Одним из основных шагов, которые нужно предпринять, является определение поведения, которое вы хотите сформировать в качестве основы вашего языка. Это поведение, которое легко сделать на вашем языке, потому что оно встроено в первый этаж. Мы принимаем дизайнерские решения о том, какие функции включить в каждый язык.

Что касается вашего конкретного примера, когда разрабатывался C, он был разработан так, чтобы работать очень близко к тому, как работали языки ассемблера того времени. Функции Variadic просто помещают аргументы в стек с минимальной безопасностью типов. Реализация этих переменных функций была оставлена ​​на усмотрение компилятора, чтобы обеспечить максимальную переносимость. Соответственно, было сделано очень мало предположений о возможностях аппаратного обеспечения. К тому времени, когда появился JavaScript, сцена изменилась. Он уже работает на виртуальной машине как интерпретируемый язык, поэтому баланс смещается в сторону удобства. Разрешение перехвата переменных функций становится разумным. Даже в случае JavaScript, который компилируется как раз вовремя, наши компиляторы готовы хранить гораздо больше дополнительной информации об аргументах, чем те, что были готовы компиляторами C ранее.

Корт Аммон
источник
1
@Wildcard Я бы посчитал (практически) все компиляторы ненадежными в этом отношении. Большинство языков являются тьюрингово-полными, но в конечном итоге их нужно интерпретировать / компилировать в ассемблер, что не так. Но это необходимое физическое ограничение - аппаратное обеспечение никогда не бывает мощным по Тьюрингу. Тем не менее, вычислимость предлагает много полезных концепций, которые в практическом смысле «применимы» к компьютерам реального мира.
Чи
3
@Wildcard В этом тривиальном смысле. Сборка (и C) имеет указатели фиксированного размера, которые могут обращаться только к ограниченному объему памяти. Теоретически мы могли бы определить сборку, в которой указатели являются неограниченными натуральными числами, но я бы больше не назвал эту «сборку» - я бы назвал это URM или что-то в этом роде. На практике мы просто притворяемся, что физические границы достаточно велики, чтобы позволить нашим программам работать, поэтому, даже если компьютер является только конечным автоматом (подразумевая, что он не может, например, выполнять сложение), мы больше думаем об этом как о машине Тьюринга ( так что добавление выполнимо).
Чи
4
@chi Это не совсем точно. Во-первых, практически все считают, что C является полным по Тьюрингу, потому что мы обычно назначаем эту фразу вокруг предположения, что «у вас достаточно памяти». Для очень небольшого числа людей, которым приходится беспокоиться о более строгой формулировке, где такие допущения являются недопустимыми, C не указывает размер указателя и не определяет границы того, сколько памяти может быть адресовано. Таким образом, даже в самом строгом смысле слова «Тьюринг завершен» C действительно является Тьюринговым завершением.
Cort Ammon
3
@CortAmmon Я должен не согласиться. Если бы мы формализовали семантику C, пытаясь внедрить допущение «достаточно памяти», мы потерпели бы неудачу, поскольку sizeof(void *)обязаны оценивать что-то по стандарту ISO C. Это заставляет нас ограничивать объем памяти для любой конкретной программы чем-то большим, но все же ограниченным. Например, я не могу написать программу, семантика которой добавляет два произвольных натуральных числа. C все еще можно сделать Turing мощным с помощью ввода-вывода, используя такие файлы, как ленты TM (как указано выше @Hurkyl). Я согласен, что это не проблема на практике.
Чи
7
Я предлагаю новый язык C-inf, который точно такой же, как C, за исключением того, что при рекурсии или выделении кучи выделяется слишком много памяти, программа прерывается, перекомпилируется с большим значением для sizeof (void *) и sizeof (size_t), и снова начинает работать с самого начала.
gnasher729
26

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

Полнота Тьюринга говорит, что «этот автомобиль может ездить везде, где может идти любой другой автомобиль». То есть вы можете вычислить все те же функции. Вход на выход, начало до конца.

Но это утверждение ничего не говорит о том, как вы туда попали. Это может быть на рельсах, это может быть на дорогах, это может быть в воздухе. Точно так же Turing Completeness ничего не говорит о том, как вы вычисляете функцию. Вы можете использовать рекурсию, итерацию или какие-то странные клеточные автоматы. Вы можете использовать типы или нет, вы можете использовать динамические или статические методы. Но если все, что вы считаете, это функции (или наборы / формальные языки), которые вы можете вычислять, пока вы выполняете Turing Complete, эти функции дают вам одинаковую мощность.

jmite
источник
4
Это отличная аналогия. Это также хорошо распространяется на вопрос, который я видел в других местах на этом сайте, о том, могут ли быть другие модели вычислений, превосходящие машину Тьюринга: в этой аналогии самолеты и космические корабли - это больше, чем Turing Complete, и быстроходные катера - еще один тип машины целиком. :)
Wildcard
2
Путешествие быстрее, чем свет, вероятно, является лучшей аналогией для вычислений супер-тьюринга. Это может быть возможно, но большинство людей думают, что это не так.
Jmite
@jmite Конечно, до сих пор нет убедительных доказательств того, что наш мозг - это сверхмощные компьютеры. Наша (очевидная) неспособность рассмотреть нетуринговые машины может быть следствием этого, хотя это не обязательно является непреодолимым барьером. Самолеты на самом деле довольно хорошая аналогия - они просто идут «прямо» между двумя точками, игнорируя местность. Если бы мы могли игнорировать топологию самого пространства-времени, мы могли бы летать и быстрее света. Не то чтобы я говорил, что можно игнорировать топологию пространства-времени, заметьте :)
Luaan
1
@Luaan Правильно, но наш мозг не обязательно должен быть супер-тьюринговым, чтобы понимать супер-тьюринговский компьютер. Я могу описать семантику машины Тьюринга, используя более слабый завершающий язык, такой как просто типизированное лямбда-исчисление, написав функцию, которая принимает ТМ и его состояние и переводит его в следующее состояние. На самом деле я не могу запустить машину на этом языке (потому что это может занять бесконечные шаги), но я могу написать, как выглядит каждый шаг.
2016 г.
@Luaan, «до сих пор нет убедительных доказательств того, что наш мозг является сверхмодульным компьютером» , - возможно, но нет также доказательств того, что человеческий разум - это всего лишь машина Тьюринга. Так как не существует машины Тьюринга, на которую можно было бы указать нигде, где нельзя отследить идеи, порожденные человеческим разумом, все еще существует различие в том, что жизнь может порождать идеи, а механические ухищрения - нет. Но что касается моделей вычислений, я думаю , что машины Тьюринга действительно включают в себя все, что можно разумно назвать «вычислениями», идеями и мечтами и тому подобное, несмотря на это.
Wildcard
17

По сути, вы спрашиваете о разнице между вычислительной мощью и тем, что обычно называют выразительной силой (или просто выразительностью ) языка (или системы вычислений).

Вычислительная мощность

Вычислительная мощность относится к тому , какие проблемы языка можно вычислить. Наиболее известным классом вычислительной мощности является тот, который эквивалентен универсальной машине Тьюринга . Существует множество других систем вычислений, таких как машины произвольного доступа , λ-исчисление , комбинаторное исчисление SK , µ-рекурсивные функции , WHILEпрограммы и многие другие. И, как выясняется, все они могут имитировать друг друга, что означает, что все они имеют одинаковую вычислительную мощность.

Это порождает тезис Черч-Тьюринга (названный в честь Алонзо Черча, который создал λ-исчисление, и Алана Тьюринга, который создал Универсальную Машину Тьюринга). Тезис Черча-Тьюринга является гипотезой вычислимости с двумя аспектами:

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

Второе, однако, более важно в области философии сознания, чем информатика.

Однако есть две вещи, о которых не говорит Тезис Черча-Тьюринга , которые очень актуальны для вашего вопроса:

  1. насколько эффективны различные симуляции и
  2. насколько удобно кодирование проблемы.

Простой пример для (1): на компьютере с произвольным доступом копирование массива занимает время, пропорциональное длине массива. Однако на машине Тьюринга это занимает время, пропорциональное квадрату длины массива, поскольку машина Тьюринга не имеет произвольного доступа к памяти, она может перемещаться по ленте только по одной ячейке за раз. Следовательно, необходимо скопировать n элементов массива n раз, чтобы скопировать их. Таким образом, разные модели вычислений могут иметь разные характеристики производительности даже в асимптотическом случае, когда мы пытаемся абстрагироваться от деталей реализации.

Примеров (2) предостаточно: и λ-исчисление, и Python полны по Тьюрингу. Но вы бы предпочли написать программу на Python или в λ-исчислении?

Есть еще одна третья морщина, которую я обходил до сих пор: все эти оригинальные системы были разработаны логиками, философами или математиками, а не учеными-компьютерщиками ... просто потому, что компьютеров и, следовательно, компьютерных наук не было. Все это восходит к началу 1930-х годов, даже до самых первых экспериментов Конрада Цузе (которые в любом случае не были программируемыми и / или не завершенными по Тьюрингу). Они говорят только о «вычислимых функциях на натуральных числах».

Теперь, как выясняется, можно многое выразить в виде функций на натуральных числах - в конце концов, наши современные компьютеры даже обходятся намного меньше (в основном 3-4 функции для чисел 0 и 1, и все) ), но, например, какую функцию выполняет операционная система?

Это понятие I / O, побочных эффектов, взаимодействующих с окружающей средой, не охвачено идеей «функций над натуральными числами». И тем не менее, это своего рода важно, поскольку, как Саймон Пейтон Джонс однажды выразился «Все чисто функции без каких - либо побочных эффектов делает, сделайте ваш процессор горячим» , к которому член аудитории ответили « на самом деле, что является побочным -эффект тоже!

Эдвин Брэди , дизайнер Idris , (только половина) в шутку использует (я не знаю, изобрел ли он его) термин «Tetris-complete», чтобы выразить эту разницу между «может вычислять любую вычислимую функцию на натуральных числах» и «может использоваться для написания нетривиальных программ, взаимодействующих со средой ". Еще более иронично, он демонстрирует это, внедрив клон Космических захватчиков в Идрисе , но он говорит, что уверен, что Тетрис превращается в Космических захватчиков.

Еще одна вещь, на которую следует обратить внимание, заключается в том, что не только эквивалентности по Тьюрингу не обязательно достаточно для того, чтобы говорить о написании «полезных» программ, но и, возможно, OTOH даже не является необходимым . Например, SQL стал эквивалентным по Тьюрингу только с ANSI SQL: 1999 , но до этого он все еще был полезен. На самом деле, некоторые могут возразить, что создание его эквивалентного по Тьюрингу вовсе не увеличило его полезность. Существует много доменных языков, которые не эквивалентны по Тьюрингу. Язык описания данных обычно нет (и не должен быть). Очевидно, что Total Languages ​​не может быть эквивалентным по Тьюрингу, но вы все равно можете записывать в них циклы событий, веб-серверы или операционные системы. Есть также языки, которые эквивалентны по Тьюрингу, но где это фактически считается ошибкой.

В общем, эквивалентность по Тьюрингу не очень интересна, если только вы не хотите статически анализировать программы.

Выразительность

Если предположить, что наша вычислительная система достаточно мощна в вычислительном отношении, чтобы вообще решить нашу проблему, то, что нам нужно сделать дальше, - это выразить наш алгоритм для решения этой проблемы в некоторой формальной записи для этой системы. Другими словами: нам нужно написать программу на каком-нибудь компьютерном языке. Вот где приходит понятие выразительности .

По сути, это означает, насколько «легко» или «приятно» писать нашу программу на нашем конкретном языке программирования. Как видите, это понятие довольно размытое, субъективное и скорее психологическое, чем техническое.

Однако есть попытки более точных определений. Самым известным (и самым строгим из известных мне) является Матиас Феллайзен в своей статье « О выразительной силе языков программирования» (первые две страницы содержат мягкое введение, остальная часть статьи более мясистая).

Основная интуиция заключается в следующем: при переводе программы с языка на другой язык некоторые из изменений, которые вам нужно сделать, содержатся локально (например, превращение FORциклов в WHILEциклы или циклов в условные GOTOs), а некоторые требуют изменения глобального Структура программы.

Когда вы можете заменить одну функцию одного языка другой функцией другого языка только локальными преобразованиями, то считается, что эти функции не влияют на выразительность. Это называется синтаксическим сахаром .

С другой стороны, если это требует изменения глобальной структуры программы, то язык, на который вы переводите, считается неспособным выразить эту функцию. И язык, с которого вы переводите, называется более выразительным (по отношению к этой функции).

Обратите внимание, что это дает объективно измеримое определение выразительности. Также обратите внимание, что это понятие зависит от контекста и является сравнительным. Таким образом, если каждая программа на языке A может быть переведена на язык B только с локальными изменениями, и есть хотя бы одна программа на языке B, которая не может быть переведена на A только локальными изменениями, то язык B строго более выразителен, чем язык, Однако более вероятный сценарий состоит в том, что многие программы на обоих языках можно переводить туда и обратно, но есть некоторые программы на обоих языках, которые нельзя перевести на другой. Это означает, что ни один язык не является строго более выразительным, чем другой, они просто имеют разные функции, которые позволяют различным программам выражаться по-разному.

Это дает формальное определение того, что значит быть «более выразительным», но все же не отражает психологические понятия, лежащие в основе этого явления. Например, синтаксический сахар, согласно этой модели, не увеличивает выразительную силу языка, потому что он может быть переведен с использованием только локальных изменений. Тем не менее, мы знаем из опыта , что наличие FOR, WHILEи IFдоступно, даже если они просто синтаксический сахар для условных GOTOмоделей выражения нашего намерения легче .

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

Пример, который я нашел в теге Ruby на StackOverflow: многие пользователи, которые следуют тегу Ruby, утверждают, что циклы легче понять, чем рекурсию, и рекурсия предназначена только для опытных функциональных программистов, а циклы более интуитивны для новичков, но я видел несколько случаев полные новички, которые интуитивно пишут такой код:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Что обычно приводит к тому, что несколько человек комментируют, что «это не работает» и «они делают это неправильно», а «правильный путь» таков:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Итак, очевидно, что есть люди, для которых хвостовая рекурсия является более естественным способом выражения концепции «зацикливания», чем конструкции цикла.

Резюме

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

Это ничего не говорит о том, как быстро они вычисляют эти функции. Это ничего не говорит о простоте выражения этих функций. И это ничего не говорит о том, что они могут делать, кроме вычисления функций на натуральных числах (например, ссылки на библиотеки C, чтение ввода от пользователя, запись вывода на экран).

Означает ли это, что класс проблем, которые каждый язык программирования может решать, зависит от языка, хотя все эти языки завершены?

Да.

  1. Существуют проблемы, которые не охватываются термином «полный Тьюринг» (который касается только вычислительных функций на натуральных числах), например печать на экран. Два языка могут быть полными по Тьюрингу, но один может разрешить печать на экране, а другой - нет.
  2. Даже если оба языка могут решать одни и те же проблемы, это ничего не говорит о том, насколько сложна кодировка и насколько легко выразить эту кодировку. Например, C может решить любую проблему, которую может Haskell, просто написав интерпретатор Haskell на C ... но сначала вы должны написать интерпретатор Haskell, чтобы решить проблему таким образом!
Йорг Миттаг
источник
7

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

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

Некоторые из них могут представлять интерес:

Euge
источник
5

Все языки, полные по Тьюрингу, могут вычислять одно и то же.

Если вы попытаетесь реализовать современный язык, вы заметите, что большинство его возможностей не добавляет вычислительных возможностей. Многие из этих функций могут быть уменьшены до более простых, которые уже существуют на одном языке.

Вот некоторые примеры:

  • Если у вас нет перечислений, вы можете использовать целые числа.
  • Если у вас нет буферов, которые знают их размер, вы можете создать тип, который содержит размер, и буфер, который не знает его размер.
  • Если у вас нет проверки границ буферов, вы можете просто проверять индекс каждый раз, когда используете их.
  • Если у вас нет функций с переменными числами, вы можете создать функцию, которая будет принимать буфер, который знает его размер, и считывать из этого буфера ту же информацию, которую вы получите из формальных аргументов.
  • Если у вас нет операторов, вы можете использовать функции.
  • Если у вас нет типов, которые могут наследовать друг друга, вы можете создавать типы, которые содержат друг друга, и обращаться к ним через дополнительный уровень косвенности, при этом подтип - это просто преобразование типа handle-to-the-all-type в ручка-к-содержащемуся типа.
  • Если у вас нет делегатов, но есть указатели на функции, вы можете создать тип, который содержит референтный объект и указатель на функцию.
  • Если у вас нет делегатов, но у вас есть интерфейсы, вы можете объявить интерфейс, который содержит один метод с нужной вам подписью.
  • Если у вас нет универсальных типов, вы можете использовать неуниверсальные типы, которые принимают только верхнюю или нижнюю границы, которые вас интересуют (и, возможно, выполняете соответствующие преобразования в местах использования, чтобы компилятор был доволен).
  • Если у вас нет системы линейного / аффинного типа, вы можете просто избегать использования любой переменной более одного раза.
  • ...и так далее.

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

Чисто вычислительные вещи были заколочены давным-давно.

Теодорос Чатзигианнакис
источник
4

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

Тем не менее, это можно сравнить выразительность языка с математической точностью. Взгляните на книгу Феллайзена « О выразительной силе языков программирования» . Грубо говоря, идея состоит в том, чтобы задать следующий вопрос: Могу ли я преобразовать любую программу на языке A в программу на языке B, внеся только локальные изменения? Другими словами, Феллайзен дает математически точную форму вашей интуиции.

rgrig
источник
2

В довершение всех остальных, вот еще одна аналогия.

Для стирки белья нужны три вещи: резервуар для воды, какое-то моющее средство и механизм перемешивания. Это может быть реализовано разными способами. Резервуар для воды - это все, что содержит достаточно воды (например, ванна, озеро, река). Механизм перемешивания может представлять собой механическое устройство, стиральную доску или даже камень, по которому бьют одежду. И моющие средства бывают разных форм тоже.

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

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

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

Псевдоним
источник
2

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

Возьмем, к примеру, язык, который выражает машины Тьюринга. Каждая программа на языке является машиной Тьюринга.

Теперь рассмотрим подъязык всех машин Тьюринга, которые читают и пишут только символы a, b и пробел. Он завершен по Тьюрингу, но не может выразить какие-либо программы, которые, например, выдают c на всех входных данных, потому что он не может писать никаких cs. Он может выражать только все вычислимые функции на входах и выходах, закодированные как строки as и bs.

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

reinierpost
источник