Re[22]: Человек - не машина Тьюринга. Почему ?
От: Alexey Rovdo Россия http://ru.linkedin.com/in/rovdo
Дата: 09.09.05 10:27
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>Здравствуйте, Alexey Rovdo, Вы писали:


AR>>Алгоритм Шора опирается на квантовое дискретное преобразование Фурье (ДПФ), которое выполняется на квантовом компьютере как чередующиеся друг за другом преобразования Адамара над отдельными кубитами и операции условного поворота фазы в одном кубите ...


AVK>Отлично. Только вот какое это имеет отношение к:

AVK>

Поэтому не путайте две разных вещи: "эмуляцию работы квантового
AVK>компьютера" и "моделирование квантового компьютера для конкретной
AVK>задачи с точно определенными параметрами".

AVK>Для пояснения таких различий тонкости алгоритма Шора совершенно не нужны.

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

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

Every function that can be physically computed can be computed by a Turing machine
(каждая функция, которая физически может быть вычислена, может быть вычислена на машине Тьюринга)


Считается, что это утверждение опровергнуто в работе: Willem Fouché, Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442

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

PS: Что же касается квантовых алгоритмов, то я не представляю себе "эмуляцию" линейного преобразования в гильбертовых пространствах ...
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.