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

[Dandan]

Circiter в сообщении #375037 писал(а):

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

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

-- Вс ноя 14, 2010 16:35:27 --

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

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

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

[epros]

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

вы хотите построить что-то непонятное. Для входа n ваше устроиство либо а) когда-нибудь даст ответ , либо б) зависнет навсегда. Третьего быть не может. Если при каком-то n оно зависнет навсегда -то значит ваше устройство считает не то, что надо. Если для любого n оно выдаст ответ через какое-то время -значит оно "гарантировано" все считает, а такого быть не может согласно ЧТ.

На самом деле мы надеемся, что второго тоже быть не может, т.е. сидим и ждём, когда устройство выдаст ответ. Если же вдруг нам удалось ДОКАЗАТЬ, что ответа не будет, то мы добавляем в конструкцию устройства соответствующую проверку на зацикливание, которая эту МТ отбраковывает.

[epros]

Circiter в сообщении #375037 писал(а):

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

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

[Ales]

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

а) когда-нибудь даст ответ $\Sigma(n)$, либо
б) зависнет навсегда.
Третьего быть не может.

"Когда-нибудь" не подходит для практики.
Разумно требовать ограничение по времени для ответа.

Реально надо делать так:
программа дает ответ за определенное время (например 10 секунд),
если 10 секунд прошло и программа не выдала ответ, она прекращает работу.

Либо есть ответ, либо Вы знаете, что за 10 секунд программа не выдает ответ.

[epros]

Ales в сообщении #376119 писал(а):

Либо есть ответ, либо Вы знаете, что за 10 секунд программа не выдает ответ

Сделам процессор в 10 раз большего быстродействия.