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

31

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

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

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

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

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

Никос М.
источник
1
есть один смысл, в котором изложенные понятия совершенно противоположны . Законы теородинамики о росте энтропии исключают вечный двигатель . nonhalting машина представляет собой вечный двигатель .
'17
да, я вижу, переосмысление состояния без остановки как вечного двигателя (2-го рода?), это точно в духе вопроса, но это то, что говорит теорема об остановке? В нем говорится, что мы не знаем, останавливается он или нет, из-за «округлости», хорошо
Никос М.
Предложение добавить «термодинамику» и / или «термодинамику-вычисление» в качестве новых тегов в CS.se? я не уверен, смогу ли я сделать это сам (вероятно), но давайте послушаем другие мнения
Никос М.

Ответы:

11

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

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

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

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

Блуждающая логика
источник
Да, есть связь с термодинамикой вычислений (Беннетт, Ландауэр и др.), Но спрашивать больше в связи с теоремой Остановки и / или отображением между TM и CE (как в вопросе), но хороший ответ
Никос М.
1
Ах, ты прав. Я понижаю свой ответ. Комментарии под вашим вопросом о том, что это не по теме, заставили меня увидеть красный, и я в основном отвечал на это. В ответ на ваш реальный вопрос: посмотрите на тезис Черча-Тьюринга. Предполагая, что вы верите в это, а также в то, что математика может моделировать что-либо в природе, тогда проблема Остановки является теоремой физической невозможности.
Блуждающая логика
я думаю , что тезис Черча-Тьюринга , что физическое вычисление является эффективным вычисление может быть необходимо на самом деле, посмотрите на этой статье также
Никос М.
5

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

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

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

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

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

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

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

Джошуа Тейлор
источник
эта статья дает многое в направлении, которое вы упоминаете, IMO. Также то, что я считаю очень важным, это округлость (или диагонализация) аргументов. Существуют направления исследований, которые связывают необратимые логические преобразования с необратимыми термодинамическими процессами (например, принцип Ландауэра и его возражения). Есть некоторые возражения против некоторых утверждений 2-го Закона, но можно найти формулировки, которые все еще сохраняются (например, работа Пригожина)
Никос М.
О том, как может возникнуть эта связь, см. Также комментарии к предыдущему ответу (только для целей правдоподобия)
Никос М.
Что касается других формулировок 2-го закона (даже более общих и для неравновесных процессов), вы можете проверить утверждение Каратеодори в терминах фазового пространства и геометрии, работы Пригогина по неравновесным системам и формулировки Хацопулоса-Гифтопулоса-Беретты (с дальнейшими связями с квантовая механика)
Никос М.
В некотором смысле там так много граней энтропии , как есть аспекты теоремы Гёделя (ов) (как в Остановках теоремы Тьюринга, теорема неопределимости Тарской , теорема россеровской в , теорема о неполноте Чайтина в ), есть даже категория теоретико-доказательство «общие Теорема Геделя ", охватывающая все предыдущие, основанная на неподвижных точках
Никос М.
Даже если связь между проблемой остановки и термодинамической энтропией достигается в том случае, если и когда справедлив 2-й закон, тогда ... , он все еще хорош, как этот вопрос (в связи с возражением, что 2-й закон может быть похож на 5-й постулат о параллелях в евклидовой геометрии)
Никос М.
4

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

Дэвид Ричерби
источник
2-й закон. Результаты невозможности имеют много общего с (математическими) логическими проблемами и кругами, может быть, здесь есть связь?
Никос М.
1
Вы должны были бы дать более подробную информацию: как я уже сказал, я не физик. Но я не понимаю, как физические законы могут оказывать какое-либо влияние на конструкцию, которая существует независимо от физической реальности.
Дэвид Ричерби
у вас есть точка зрения, я могу привести много эпистемологических причин, почему это очень правдоподобно (например, математика, которую мы действительно зависим от мира, в котором мы живем , а-ля Эйнштейн), но я хочу чего-то еще, если бы у меня был готовый ответ, я вероятно опубликовал бы статью :)
Никос М.
2
@vzn Мы используем слово «время» для числа шагов, которые машина выполнила, и «пространство» для количества используемых ленточных ячеек, но эти слова были выбраны, чтобы обратиться к нашей физической интуиции как к физическим существам. Но «время» - это просто указатель на последовательность конфигураций, а пространство - это просто указатель на последовательность символов. Например, рассмотрим машину Тьюринга, в которой голова просто свистит вправо. Он использует бесконечное «время» и бесконечное «пространство», но вы можете понять это в конечном количестве реального времени и реального пространства
Дэвид Ричерби
2
Конечно, но тот факт, что мы рассматриваем машины Тьюринга как интересные объекты, может иметь какое-то отношение к физике.
Жиль "ТАК - перестань быть злым"
1

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

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

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

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

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

ВЗН
источник
можно
подробно рассказать
см. также CS defn от entropy stackoverflow
vzn
интересно уметь мыслить «из коробки» (по крайней мере, иногда), вы изучали работу Беннета по термодинамике вычислений? Мотивация вопроса заключается в том, чтобы показать, можно ли рассматривать теорему остановки как следствие термодинамики (с некоторой подходящей моделью или представлением, по крайней мере, для некоторых случаев). я думаю, что было бы действительно интересно, если бы это могло быть решено в любом случае
Никос М.
возможно, вы уже видели эти документы, philsci-archive.pitt.edu/313/1/engtot.pdf и cc.gatech.edu/computing/nano/documents/…
Никос М.
Большинство понятий «энтропия», используемых в информатике, относятся либо к теории информации Шеннона, либо к теории алгоритмов информации Колмогорова / Чайтина / Соломонова, это уже упоминалось в вопросе и очень важно. Единственные связи с термодинамической энтропией, которые мне известны (которые могут быть связаны с инф. Энтропией), - это термодинамика вычислений. Вопрос связан с термодинамикой вычислений, но по-другому
Никос М.
1

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

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

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

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

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

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

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

user13675
источник
Хороший ответ: часть, связанная с нагревом лампочек, многократно используется как связь между информационной энтропией и термодинамической энтропией (это противоречит мнению Джейнса как субъективной неопределенности). моя собственная точка зрения заключалась бы в том, чтобы основывать свои рассуждения на округлости обеих конструкций и на том, что (умный?) каскад один с другим создает подтекст (по крайней мере, так или иначе)
Никос М.
Аналогичные рассуждения используются с батареями (вместо лампочек), чтобы определить, какие батареи разряжены ...
Никос М.
0

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

Первый шаг

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

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

Второй шаг

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

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

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

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

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

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

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

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

Hernan_eche
источник
1
Я не понимаю связь с проблемой остановки. Во-первых, вы, кажется, переопределили, что означает остановка машины. Во-вторых, кажется, у вас есть только одна программа (симулятор частиц газа). Вполне возможно доказать, что одна фиксированная программа останавливается или не останавливается, не нарушая неразрешимость общей проблемы остановки.
Дэвид Ричерби
О остановке, она не переопределяет остановку, здесь остановка программы, как всегда, когда программа завершает вычисления, и вы получаете вывод, поэтому здесь вывод определяется как точный момент, когда частица с правильной скоростью ударила в дверь , и вы можете построить дверь, которая обнаружит ее, поэтому она будет отмечать, когда программа останавливается (затем программа запускается снова из этих начальных условий для другого выхода). Демон хочет знать, когда он остановится, но он не может знать, даже если он остановится.
Hernan_eche
1
Машины Тьюринга не могут решить проблему остановки машин Тьюринга. Кажется, что вы переопределили проблему остановки как «Делает ли одна из этих молекул газа когда-либо X?», Что является совершенно другой проблемой, чем «Останавливается ли эта машина Тьюринга при запуске с этим вводом?» Доказательство Тьюринга неразрешимости проблемы остановки машины Тьюринга ничего не говорит о том, может ли машина Тьюринга вычислить, будет ли когда-нибудь молекула газа совершать Х.
Дэвид Ричерби,
Комментарий Дэвида правильный, так как он не связан напрямую с проблемой остановки. Однако это аргумент, который следует духу вопроса
Никос М.
1
@ Жиль, спасибо, что заметили, я согласен с этим, если потребуется, будет создан чат. Я бы предпочел оставить эти комментарии, тем не менее, так как они касаются как вопроса, так и конкретного ответа (по мере развития)
Никос М.
-1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Джером
источник
1
«Райс утверждает, что никакие машины Тьюринга не могут бесконечно производить нетривиальное свойство». Это не парафраз Райс, который я узнаю. Что вы имеете в виду?
Дэвид Ричерби
1
Что вы имеете в виду под "бесконечно производить нетривиальное свойство"?
Дэвид Ричерби
Немного искривлено. Райс говорит, что нельзя доказать, что ТМ реализует данную функцию. Теперь, если TM A выдает неопределенно нетривиальное свойство (N-TP), это означает, что он создает N-TP для ЛЮБОЙ записи. Как это может быть правдой на практике? Что ж, похоже, единственный способ для этого быть правдивым - рассмотреть неопределенную запись e и показать, что ее A (e) имеет N-TP. По очереди это означало бы, что нам удастся доказать, что машина производит N-TP. И мы знаем, что это невозможно. В сущности, я постулирую, что это равносильно тому, что «А производит бесконечно N-TP» и «Я МОГУ ПОКАЗАТЬ, что А производит N-TP»
Джером,
«Бесконечно создавать нетривиальное свойство» означает, что вы можете добавить бесконечное количество различных записей в TM. И все выходы будут иметь NT-P
Джером
1
ХОРОШО. Я думаю, что ваш ответ был бы намного яснее, если бы вы просто использовали стандартные термины вместо того, чтобы придумывать такие вещи, как «бесконечно производить нетривиальное свойство», что означало бы «быть способным обрабатывать бесконечное количество входных данных». Это также поможет объяснить, какой аспект вашей «настоящей» машины Тьюринга не способен обрабатывать бесконечное количество входных данных. Например, лента конечна?
Дэвид Ричерби