физический тезис Черча-Тьюринга

[Munin]

Физический способ проверки, ещё работает или уже нет: проверить, греется или не греется :-)

[Dandan]

а если не греется и ничего не выдал - значит сломался

[Someone]

myhand в сообщении #372730 писал(а):

Someone в сообщении #372724 писал(а):

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

Мне помнится другая формулировка тезиса: "любой алгоритм может быть реализован машиной Тьюринга". Алгоритм - понятие менее укладывающееся в Ваш пример.

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

http://matem.uspu.ru/i/inst/math/subjects/A08DPPMAT_LEC2007D01.pdf
http://matem.uspu.ru/i/inst/math/subjects/A08DPPMAT_LEC2007D02.pdf
http://matem.uspu.ru/i/inst/math/subjects/A08DPPMAT_LEC2007D04.pdf

myhand в сообщении #372730 писал(а):

Someone в сообщении #372724 писал(а):

В данном случае "закон" состоит в том, чтобы подождать, когда очередной нейтрон распадётся, и зафиксировать момент распада (я встречал аналогичный пример в какой-то статье об интуиционизме).

Тут что-то многозначное получается - нет? Я так понял. У Вас есть система в одном состоянии, "вход". Через некоторое время в другом (один нейтрон распался). Время этого распада - "выход". Надеюсь, что основная идея понятна.

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

Dandan в сообщении #372744 писал(а):

Под физическим устройством будем понимать черный ящик со входом и выходом. На вход мы подаем число и на выходе получаем число.

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

Как я уже говорил, никакого "физического тезиса Чёрча" мы не докажем, поскольку даже "математический" тезис Чёрча доказать заведомо нельзя.

[Dandan]

Someone в сообщении #372841 писал(а):

Дело в том, что число - это абстрактное понятие, и "подать" его на "вход" или "получить" на "выходе" физической системы нельзя. Мы можем в качестве "входа" оказать на систему какое-то физическое воздействие, которое мы хотим интерпретировать как число (а почему обязательно число?), а определённые реакции системы мы можем интерпретировать как "выход".

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

[myhand]

Someone в сообщении #372841 писал(а):

Вы имеете в виду, что начальное состояние не определяет однозначно моменты распада? Я именно по этой причине такой пример взял, поскольку (в рамках современных физических теорий) никаким "механическим" способом эти моменты вычислить заведомо нельзя (правда, один астролог, когда я ему этот пример привёл, заявил, что я не знаю всех возможностей астрологии; только не затевайте со мной спор об астрологии, я её считаю очень глупым суеверием).
Я говорил о том, что в интуиционистской математике понятие (эффективной) вычислимости не ограничивается механической вычислимостью.

Ваш пример напоминает мне генератор случайных чисел. Убейте - не могу назвать это вычислением чего-либо.

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

С другой стороны - постановка вопроса выглядит несколько "математичной":

Dandan в сообщении #372635 писал(а):

Можно ли в некотором смысле этот физический тезис доказать? Т.е. задать некоторую простую систему аксиом физики и в этой системе доказать физический тезис ЧТ.

Ну, взять "мир" каких-нибудь клеточных автоматов и запросто "доказать". Только физики не останется.

[Dandan]

myhand в сообщении #372969 писал(а):

Ну, взять "мир" каких-нибудь клеточных автоматов и запросто "доказать". Только физики не останется.

через мир клеточных автоматов доказать ЧТ можно, но можно ли реальный наблюдаемый мир объяснить через мир клеточных автоматов? Если да, то ответ принимается
Хочется имено такую систему аксиом, которая также может объяснить наблюдаемые физические явления (помимо того, что в ней можно будет доказать ЧТ).

[myhand]

Dandan в сообщении #373040 писал(а):

но можно ли реальный наблюдаемый мир объяснить через мир клеточных автоматов? Если да, то ответ принимается

Про "реальный наблюдаемый мир" Вам привели совершенно конкретный пример нарушения ЧТ (квантовая механика).

[epros]

Dandan в сообщении #372744 писал(а):

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

В такой формулировке "тезис" даже в математике можно опровергуть. Пример - Busy beaver - функция, которая доказанно является well defined (т.е. определена для каждого натурального аргумента), однако доказанно невычислима (т.е. не может быть смоделирована машиной Тьюринга).

Dandan в сообщении #372814 писал(а):

при этом если мы ничего не получили в какой-то момент времени после запуска - значит ЧЯ еще работает, и, возможно, в будущем что-то выдаст. А может и не выдаст.

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

myhand в сообщении #373082 писал(а):

Про "реальный наблюдаемый мир" Вам привели совершенно конкретный пример нарушения ЧТ (квантовая механика).

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

[myhand]

epros в сообщении #373498 писал(а):

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

Дак Вы определитесь там. Вам нужон реальный мир, али как?

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

[epros]

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

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

[Dandan]

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

[epros]

На самом деле непонятного много.

Во-первых, непонятно, что такое:

Dandan в сообщении #373646 писал(а):

устройство, которое будет в некотором смысле вычислять определенную функцию

Ибо если некий чёрный ящик после подачи ему на вход нескольких чисел выдал несколько чисел на выходе, то это ещё не означает, что он реализует некую математическую функцию $\mathbb{N} \to \mathbb{N}$. Что нас должно убедить в том, что это именно так?

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

В третьих, непонятно, что Вы считаете достаточным "объяснением", когда говорите вот это:

Dandan в сообщении #373646 писал(а):

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

Если теория просто постулирует это (и при этом она является вполне "физической" - согласно предполагаемой сфере своего применения), то это для Вас будет достаточным "объяснением"?

-- Пт ноя 12, 2010 12:40:11 --

Кстати, устройство для вычисления "всяких бобров" мы построить как раз можем, вот только мы не сможем убедиться в том, что оно действительно вычислит $\Sigma(n)$ для любого заданного $n$: Для некоторых $n$ ждать придётся очень долго, возможно, что не дождёмся...

[Dandan]

1. у нас есть схема устройства и мы знаем законы физики. Это и убедит нас в том, что устройство работает на вычислении функции.
Мой вопрос-запрос - указать такие законы физики, из которых следует, что не существует схемы устройства, которое вычисляет busy beaver.

2. физическая теория, как вы правильно заметили, это теория, которая объясняет физические явления. Возможность или невозможность построить определенное устройство это тоже физическое явление, как по мне.

3. "объясняет" в том смысле, в котором механика Ньютона объясняет, почему Луна не падает на Землю.

-- Пт ноя 12, 2010 11:11:36 --

epros в сообщении #373918 писал(а):

Кстати, устройство для вычисления "всяких бобров" мы построить как раз можем, вот только мы не сможем убедиться в том, что оно действительно вычислит $\Sigma(n)$ для любого заданного $n$: Для некоторых $n$ ждать придётся очень долго, возможно, что не дождёмся...

не совсем понимаю как вы такое устройтсво собираетесь построить.

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

[epros]

Dandan в сообщении #373926 писал(а):

1. у нас есть схема устройства и мы знаем законы физики. Это и убедит нас в том, что устройство работает на вычислении функции

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

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

Dandan в сообщении #373926 писал(а):

Мой вопрос-запрос - указать такие законы физики, из которых следует, что не существует схемы устройства, которое вычисляет busy beaver

Откуда же эти законы возьмутся? Чтобы появились "законы физики", сначала должны появиться теоретики, которые их сформулируют. Если Вас сам тезис ЧТ в качестве такового "закона физики" не устраивает, значит у нас такого закона и нет. Математика говорит нам только то, что busy beaver не моделируется машиной Тьюринга. Это тесно связано с алгоритмической неразрешимостью проблемы останова любых алгоритмов: Если бы существовал универсальный алгоритм, разрешающий проблему останова, то из него можно было бы построить алгоритм, который бы положительно отвечал на вопрос о собственной неразрешимости (что противоречиво). Однако это не мешает нам верить в существование физического устройства, которое могло бы ответить на вопрос о разрешимости любого алгоритма. С помощью такого устройства можно было бы построить вычислитель функции $\Sigma(n)$. Но можно верить и в НЕ существование такого устройства, т.е. в "физический" тезис ЧТ.

Dandan в сообщении #373926 писал(а):

Возможность или невозможность построить определенное устройство это тоже физическое явление, как по мне

Это не совсем точно. Возможность или невозможность - это всё-таки теоретические понятия. Физическое явление же - это нечто наблюдаемое. Нельзя наблюдать "возможность", а тем паче - "невозможность".

Dandan в сообщении #373926 писал(а):

3. "объясняет" в том смысле, в котором механика Ньютона объясняет, почему Луна не падает на Землю

Механика Ньютона постулирует закон всемирного тяготения. Из него (а также из трёх законов Ньютона) и делается тот вывод, что Луна не должна упасть на Землю. Физическое же явление (которое мы наблюдаем) - это тот факт, что она до сих пор не упала. Что позволяет нам верить в состоятельность Ньютоновской механики.

-- Пт ноя 12, 2010 14:05:41 --

Dandan в сообщении #373926 писал(а):

не совсем понимаю как вы такое устройтсво собираетесь построить

Говоря "можем построить" я не имел в виду, что устройство, которое мы построим, будет гарантированно вычислять $\Sigma(n)$. Но можно построить нечто, которое будет в какой-то части симулировать вычисление этой величины. Т.е. оно, например, конструирует и запускает машины Тьюринга, а для тех, которые достаточно быстро не останавливаются, выполняет некоторое конечное множество проверок на разного рода "зацикливания". Естественно, может остаться некоторое количество машин Тьюринга, которые не остановились (пока), но и не были отбракованы ни одной из проверок на "зацикливания" ... Но мы будем надеяться, что таковых не будет, сядем и будем ждать, когда наше устройство даст ответ ...

[Circiter]

2Dandan

Цитата:

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

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

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

2Someone

Цитата:

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

Вспомнился программерский анекдот (о получении даты завтрашнего дня):

public Calendar getTomorrow()
{
    Thread.sleep(1000*60*60*24);
    return Calendar.getInstance();
}