Есть ли связь между проблемой остановки и термодинамической энтропией?

Алан Тьюринг предложил модель для машины (Turing Machine, TM), которая вычисляет (числа, функции и т. Д.), И доказал теорему Остановки .

ТМ - это абстрактное понятие машины (или двигателя, если хотите). Теорема Остановки - результат невозможности. Двигатель Карно (CE) - это абстрактное понятие теплового двигателя, и Карно доказал теорему Карно , еще один результат невозможности, связанный с термодинамической энтропией.

Учитывая, что ТМ физически реализуема (хотя бы столько же, сколько СЕ, а может и нет?), Существует ли отображение или представление или «изоморфизм» ТМ или СЕ, который может позволить унифицировать эти результаты и, кроме того, соединиться с энтропией?

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

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

Я совсем не эксперт в этой области, но я верю, что вас заинтересуют обратимые вычисления . Это включает, помимо прочего, изучение взаимосвязи между процессами, которые являются физически обратимыми, и процессами, которые являются логически обратимыми. Я думаю, было бы справедливо сказать, что «основателями» этой области были / являются Ральф Ландауэр и Чарльз Х. Беннетт (оба из исследования IBM, я думаю).

Он затрагивает квантовые вычисления и квантовую теорию информации, но также рассматривает вопросы типа «каковы пределы вычислений с точки зрения времени, пространства и энергии?» Известно, (если я правильно помню), что вы можете сделать энергию, необходимую для выполнения обратимого вычисления, сколь угодно малой, сделав так, чтобы это занимало произвольно много времени. Таким образом, энергия времени (= действие ), необходимая для выполнения обратимого вычисления, может быть сделана постоянной. Это не относится к необратимым вычислениям.$\times$

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

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

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

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

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

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

Таким образом, оба случая связаны со строительством:

• Предположим, что некоторый X обладает свойством P.
  • От X, построить связанный Y.
  • Отношения между X и Y противоречивы.
• Следовательно, X не обладает свойством P.

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

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

на этот разносторонний вопрос по нескольким темам нет простого / легкого ответа, и он затрагивает активные области исследований TCS. однако это редкий вопрос о связи между физикой и TCS, который интересовал меня на протяжении многих лет. Есть несколько разных направлений, чтобы пойти на это. основной ответ заключается в том, что это «открытый вопрос», но некоторые активные / современные исследования касаются его и намекают на связи.

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

• энтропия действительно проявляется в CS, но больше в форме теории информации и теории кодирования. рождение теории кодирования включало определение / анализ энтропии, связанной с кодами связи Шенноном. попробуйте этот замечательный онлайн- справочник «Энтропия и теория информации » Грея

• Энтропия также иногда ассоциируется с измерением случайности в PRNG. В известной статье Разборова / Рудича " Разборов / Рудич" существует связь разделений классов сложности (например, P =? NP) с PRNG . на эту тему продолжаются исследования.

• Вы упоминаете термодинамику и ее связь с TCS. Существует глубокая связь между намагниченностью в спиновых стеклах в физике и полными задачами NP, изученными в точке перехода SAT. там (опять же) физическая система имеет связанную с ней энтропию, но, вероятно, она изучалась больше в контексте физики, чем в контексте TCS.

Существует простая проблема мышления, которая иногда используется в качестве введения в нетрадиционные компьютерные парадигмы:

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

Большинство компьютерных ученых обычно пытаются найти какое-то решение на основе логической логики. Ответ (по крайней мере, один из них): прикоснувшись к лампочке и увидев, какая из них горячее.

Основанные на теплоте парадигмы существуют в компьютерной науке: имитация отжига является известным алгоритмом (квантовый компьютер D-волн является квантовым аналогом алгоритма).

Есть ли связь с проблемой Остановки?

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

Короче говоря, число Омега - это вероятность того, что случайная программа остановится. Знание константы позволило бы перечислить все действительные математические утверждения (истины, аксиомы и т. Д.) И является неисчислимым. Calude вычислил версию Omega, изменив единообразную меру вероятности на меру, обратно пропорциональную длине произвольной программы, и используя кодирование без префиксов. Так что мы можем говорить об Omega Чейтина и Omega Calude.

Да !, как ни странно, я думал об этом .. Вот идея:

Первый шаг

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

Предположим, что демон не может измерить скорость, с которой частицы попадают в дверь, почему? потому что это изменило бы скорость частиц, поэтому демон должен выяснить, прежде чем открыть его, не глядя, не измеряя. Чтобы быть справедливым, мы дадим демону заранее знать правила игры, т. Е. Снабдить демона законами движения, взаимодействиями частиц и начальными условиями, достаточными для физики / динамической модели.

Второй шаг

Теперь смоделируйте газ частиц также как компьютерную программу, которая выполняет один и тот же код, который дается демону для каждой частицы, поэтому газ вычисляет результат из своих начальных условий, демон не знает этого результата, пока не остановится (если вообще ): а именно «частица с правильной скоростью находится у двери», решение «да / нет», которое мы задаем системе: «У частицы есть правильное положение и достаточная скорость?», если это так, дверь может быть открыта и быстрая частица может перейти в высокотемпературную сторону комнаты, устанавливая новые начальные условия (будут ли у этих последовательных проблем ответ? или они будут работать вечно?)

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

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

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

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

(Иногда все ограничения кажутся одинаковыми ..)

Подробнее о законах частиц

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

Действительно очень увлекательный вопрос, и мы увидим, что ваше мышление верно .

Сначала давайте посмотрим, что говорит второй принцип термодинамики.

Функция энтропии используется во 2-м законе термодинамики. Это вытекает из теоремы Карно, которая гласит, что процессы, происходящие в паровых машинах, имеют КПД ниже или в лучшем случае равны соответствующей «обратимой» машине (что, кстати, кажется нестабильным понятием в течение 150 лет термодинамики). Карно сам не использовал функцию энтропии, но вместе с Клаузиусом они говорят следующее:

Поскольку нет вечного двигателя, мы можем построить функцию S, называемую энтропией, которая ограничивает макроскопические термодинамические меры в определенном уравнении, а именно, что S (V, T, P и т. Д.) = 0

Отметим, что это уравнение есть не что иное, как уравнение гиперповерхности в пространстве термодинамических мер.

Входит в Каратеодори.

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

После перечисления определенного количества аксиом ему удается сформулировать второй закон ЕГО, который гласит (более или менее):

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

Теперь это ОЧЕНЬ отличается от формулировки Клаузиуса! Но на самом деле это не так. Все, что сделал Каратеодори, - это изменил порядок слов, как математики, игравшие с пятой аксиомой Евклида в течение 2000 лет и создававшие много разных формулировок для этой аксиомы. И если вы сделаете шаг назад, вы не должны быть слишком удивлены заявлением Каратеодори о втором законе. Фактически, Каратеодори приводит к точно такой же энтропийной функции и уравнению гиперповерхности S (V, T, P и т. Д.) = 0

Подумай над теоремой Карно. Как математик, вы не должны быть слишком довольны тем, что Карно допускает, что вечные машины не существуют. На самом деле, как математик, вы бы предпочли что-то вроде этого:

Существует энтропийная функция S, которая ограничивает макроскопические меры ЕСЛИ И ТОЛЬКО ЕСЛИ нет вечных машин ».

ТЕПЕРЬ у тебя есть теорема. И что это говорит? До тех пор, пока не существует изолированной механической системы, которая производит бесконечное количество энергии и, следовательно, может привести вас к любому состоянию, которое вы хотите, тогда вы найдете функцию энтропии. Изолированная механическая система является адиабатическим процессом. Отсюда формулировка Каратеодори: ни одна адиабатическая система никуда вас не приведет. Иногда вам понадобится немного тепла.

Так что мы не только уверены, что Каратеодори прав, но и что его формулировка довольно проста.

Откуда у вас создается впечатление, что второй закон Каратеодори похож на проблему остановки?

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

Разве это не звучит ТОЧНО, как проблема остановки? Т.е. как только вы напишете все аксиомы своей теории и изложите все возможные переходы, возникнут проблемы, которые вы не сможете решить. Иногда вам нужно будет добавить больше аксиом.

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

Что вы думаете?

ПРИМЕЧАНИЕ. Я почти полностью отредактировал свой ответ, чтобы приведенные ниже комментарии не соответствовали его содержанию.