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

[Dandan]

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

[whiterussian]

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

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

Здесь слово "физическое" к физике не имеет никакого отношения. Здесь слово "физическое" имеет смысл - реальное, существующее.

Поэтому поставленный вопрос теряет смысл.

[Someone]

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

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

Этот тезис (как и эквивалентные ему тезисы Маркова, Поста и т.д.) и в математике нельзя доказать. По тривиальной причине: "любая вычислимая функция" в этом тезисе - не математическое понятие, поскольку не имеет математического определения. Доказать что-либо математически в такой ситуации нельзя. В действительности этот тезис просто утверждает, что математическая формализация наших интуитивных представлений о вычислимости, представленная машиной Тьюринга, является адекватной. В это можно верить, а можно и не верить. Например, в интуиционистском направлении математики представление о вычислимости более широкое (Справочная книга по математической логике. Часть IV. Теория доказательств и конструктивная математика. Москва, "Наука", 1983. Глава 5. А.С.Трулстра. Аспекты конструктивной математики. § 4. Реализуемость и тезис Чёрча.).

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

[myhand]

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

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

А что заставляет Вас думать, что тут имеет место быть "вычислимая функция"?

[Someone]

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

[myhand]

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

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

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

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

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

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

[Dandan]

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

[Николай]

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

Важно то, что подавая одно и тоже число на вход - мы будем получать один и тот же ответ на выходе.

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

[Dandan]

я имел ввиду

Цитата:

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

Ясно что не любой черный ящик будет себя одинаково вести при одинаковых числах, поданных на вход.

[Maslov]

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

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

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

черный ящик со входом и выходом. На вход мы подаем число и на выходе получаем число.

А как Ваш чёрный ящик будет вести себя в случае, если вычисляемая им функция не определена для аргумента, поданного на вход?

[Dandan]

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

[Maslov]

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

черному ящику, который на входе ожидает только натуральные числа (нас собсно только такие ЧЯ и интересуют), комплексное число подсунуть на вход не получится =)

Речь не о подсовывании комплексного числа вместо натурального, а о том, что реализуемая ящиком функция $\mathbb N \to \mathbb N $ может быть определена не для всех значений аргумента.

Для примера можно взять вычислимую функцию, принимающую на входе значение $n$ и возвращающую на выходе позицию в десятичном разложении числа $\pi$, начиная с которой подряд идут $n$ девяток.

[Dandan]

ну так же как и машины Тьюринга могут "зависать", так и наш ЧЯ может зависнуть при подсчете аргумента. Это не запрещается.

[Maslov]

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

На вход мы подаем число и на выходе получаем число.

Другими словами, правильная формулировка такая: "На вход его мы подаем число и на выходе получаем число или ничего не получаем".
Так?

[Dandan]

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