Есть ли название для «физических вещей, из которых можно построить машину Тьюринга»?

16

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

Тем не менее, физический субстрат не совсем не имеет значения. Люди обнаружили, что определенные наборы компонентов, в частности, диодно-резисторная логика, являются «неполными»: независимо от того, сколько из них вы подключаете к источнику питания и друг к другу, есть определенные очень простые вещи, которые он не может делать. (Диодно-резисторная логика может реализовывать И, ИЛИ, но не может реализовывать НЕ). Кроме того, некоторые способы соединения компонентов, в частности однослойный персептрон , «неполны»: есть некоторые очень простые вещи, которые они не могут сделать. (Однослойный персептрон может реализовывать AND, OR, NOT, но не может реализовать XOR).

Есть ли менее неловкая фраза для «физических вещей, из которых можно построить машину Тьюринга»? Или, напротив, «физические вещи, которые, независимо от того, сколько их у человека, не могут образовать машину Тьюринга»?

Некоторое время я использовал фразу «функционально полный набор» или «универсальный набор ворот» - или, говоря математикам, «физические вещи, которые могут реализовать функционально полный набор» - но мне сказали, что это не так. не совсем правильно. Некоторые наборы компонентов могут реализовывать функционально полный набор; и все же невозможно построить машину, полную по Тьюрингу, полностью из этих компонентов. Например, лампочки и 4-полосные выключатели с ручным управлением могут реализовывать функционально полный набор (И, ИЛИ, НЕ, XOR и т. Д.); и, тем не менее, невозможно построить машину, полную Тьюринга, полностью из выключателей света и лампочек, так как выход (электрический или оптический) одного не может быть подан на вход (вращающегося механически) следующего.

связанный: есть ли официальное название для понятия «многоразово универсальный»? и есть ли название «чипы, из которых можно построить процессор»?

Дэвид Кэри
источник
1
Это не ответ, но я не могу оставлять комментарии, и я чувствовал необходимость дать ссылку на этот невероятный комикс xkcd: [Bunch of Rocks] [1], который связан с этим вопросом :). [1]: xkcd.com/505
Zenon

Ответы:

3

Я считаю, что подходящий термин - это «физическая реализация машины Тьюринга».

пNп, поэтому вряд ли компьютерщик разрешит их.

Вы можете прочитать больше в статье Скотта Ааронсона « Задачи и физическая реальность» , особенно в разделе «Аналоговые и относительные вычисления».

Вы также можете найти реализацию lego (с конечной лентой) на следующей странице: http://legoofdoom.blogspot.com/

chazisop
источник
+1 за Лего - вот где! Я надеялся, что мне будет легче найти фразу, которая звучит не так, как «Физическая реализация машины Тьюринга может быть составлена ​​из этого набора частей» - но это все же намного лучше, чем альтернативы, которые я видел до сих пор.
Дэвид Кэри,
4

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

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

Мартин Шварц
источник
Этот текст упакован с интересными понятиями и терминологией. Увы, я не вижу здесь ни одной фразы, которую я мог бы использовать как «Это набор <фраза> компонентов, тогда как это набор <не фраза> компонентов».
Дэвид Кэри
3

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

Вы должны посмотреть на работу Чарльза Бэббиджа и людей, которых он вдохновил. Бэббидж создал физический компьютер для табулирования полиномиальных функций в печатные таблицы для индексов Math (в те времена у вас были стопки книг, в которых не было ничего, кроме имен функций, за которыми следовали листы значений f (x)). Затем он начал работать над тем, что стали полноценным компьютером Тьюринга, использующим винтики и т. д. Я полагаю, что его сын продолжил свою работу, и единственным физическим проявлением их объединенных усилий был полностью функционирующий механический АЛУ, который является основой тех механических калькуляторов, о которых вы можете знать или не знать. Однако финансирование этих проектов в виде механического компьютера сократилось по размеру и способу, которым они могли быть сделаны в то время, было очень непрактично. Однако с тех пор, и особенно в недавних событиях, люди прошли и продолжают исследования Чарльза Бэббиджа. Этот подход может показаться его последним смехом, поскольку есть те, кто считает, что единственный способ сделать последовательные процессоры более быстрыми, чем сейчас, - это реализовать некоторые из этих механических подходов в процессоре, предотвращая проблемы, возникающие из-за электромагнитных помех, в масштабе, меньшем, чем тот, который мы используем сейчас. Механика работает в любом масштабе, казалось бы.

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

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

acp10bda
источник
Лампочки и выключатели света можно реализовать NAND. Существует конфигурация из двух обычных выключателей света и выходной лампочки (и второй скрытой лампочки), в которой выходная лампочка остается ЯРКОЙ, за исключением случаев, когда человек поворачивает оба переключателя в положение ВКЛ, тогда выходная лампочка становится ТЕМНОЙ. Увы, по-видимому (?) Невозможно построить машину, полную Тьюринга, полностью из выключателей и лампочек. Есть ли какой-то термин, который я могу использовать, который включает NAND 74HC132, но исключает NAND переключатели освещения и лампочки?
Дэвид Кэри
Проблема в том, что вход является механическим, а выход - электрическим, поэтому переключатели похожи на преобразование и вентиль между двумя доменами (кинетика для электроники). Предполагая, что он функционирует точно так же, как nandgate, вы МОЖЕТЕ сделать из них полный компьютер Тьюринга, просто вам нужно будет облегчить преобразование между этими двумя средами, чтобы сделать вывод из одного шлюза входным для другого, возможно, переключателем с электроприводом, но да непрактично. Термин, который вы могли бы использовать, который я сейчас просто придумаю, это nandgate того же среднего уровня, который подразумевает, что вход и выход будут в одном и том же носителе.
acp10bda
+1 хорошая идея - просто придумайте термин и определите, что это именно тот термин, который я ищу. Набор {(блок с 2 входными световыми переключателями и выходной лампочкой, который реализует AND), (активируемый светом переключатель с электроприводом, который реализует NOT)} является d-универсальным каскадным набором. Но набор {lightbulbs, lightswitches} сам по себе не является d-универсальным каскадным набором.
Дэвид Кэри
Можно ли построить машину Тьюринга из вещей, которые не являются нандгейтами того же среднего уровня?
Дэвид Кэри,
Извините за опоздание этого ответа, но да. Машина Тьюринга может быть изготовлена ​​из любой сборки компонентов с использованием любого разнообразия входных и выходных сред при условии, что компоненты расположены таким образом, что в результате получается полный механизм Тьюринга. Однако, учитывая, что среда вычислений станет настолько дикой и потенциально очень интересной для наблюдения за работой, я бы хотел назвать такой механизм полным механизмом Рубе-Голдберга-Тьюринга. :)
acp10bda