From Sem@KremKond.poltava.ua Thu Oct 26 19:35:03 2000
Newsgroups: relcom.sci.philosophy
Subject: Вычисления бывают разные: простые, квантовые и ... безобразыне
From: "Aleksandr Semenov"
Date: Thu, 26 Oct 2000 13:35:03 +0300
--------
Evgenij Barsukov пишет в сообщении <3a106a31.486049070@usenet.seri.re.kr>
...
>ПС: Кстати интересный вопрос - существую ли задачи, алгоритм решения
>которых _фундаментально_ не может быть сделан последовательным?
Не существует.
Во всяком случае это так если тезис Черча справедлив
(а народ к этому склоняется).
И если это так то распараллеливание не такая уж и панацея, как
думают сторонники нейросетевых технологий.
Дело в том что распараллеливая задачу мы линейно увеличиваем
скорость обработки. Не более!
Если мы разбиваем задачу на 2 потока -уменьшаем время счета
в два раза (в лучшем случае!).
3 потока -в три раза.
4 потока- в четыре раза:
...
N-потлоков в N-раз.
Но задачи, время выполнения которых растет пропорционально длинен входа -
просто подарок судьбы. Дай бог что бы время возрастало хотя бы по
показательной функции!
Объясню.
Например алгоритм вычисляет функцию F(Х) за N шагов, если Х имеет длину К.
Теперь если мы на вход этой же вычислительной функции дадим Х длинной в
2K то некоторым алгоритмам потребуется приблизительно 2N шагов (линейная
зависимость),другим потребуется уже N^2 шагов (показательная зависимость).
Но самые интересные задачи (типа задачи о коммивояжере) такие, когда
время растет экспоненциально.
Мы тут со Снарским без конца строим именно такие алгоритмы как математики
не вдаемся в подробности того осуществимы они на практике или нет. Для нас
главное что бы они теоретически существовали или не существовали.
Но теоретическая осуществимость алгоритма не гарантирует его практическую
осуществимость (и в приложении к проблеме ИИ это действительно важная
проблема).
Например, легко перечислить все возможные комбинации булевых высказываний
из композиции 9-и переменных. Существует простой перечисляющий алгоритм.
Но этот алгоритм имеет экспоненциальную зависимость входа от выхода,а время
его вычисления -еще больше!
Число возможных булевых комбинаций определяется как 2^n^n
Для 9 это 2^9^9 =2.4*10^24 .
С момента образования вселенной прошло 15 000 000 000*365*24*60*60 с
Это 4.73*10^17 секунд. Сколько комбинаций надо выписывать в секунду что бы
начав с образования вселенной к настоящему моменту закончить?
10 000 000 комбинаций в секунду!
А если станем перечислять все комбинации из 10 булевых переменных?
Интересно, сколько мы успеем перечислить до конца света?
Допустим полный цикл расширени- сжатия вселенной - 200 000 000 000 лет.
Тогда оказывается что уже 11-12 комбинаций - это физический предел.
Скорость вычислителя ведь ограничена скоростью света!
Считаются практически вычислимыми задачи в которых время выполнение
зависит от длинны входа как показательная функция (x^2, x^3.... x^n)
Если мы имеем экспоненту ( n^x) задача считается практически невычислимой
при большой длине входа (а именно такая длина обычно и бывает).
Чего же стоит распараллеливание, если оно дает только линейный прирост
скорости выполнения по сравнению с последовательным алгоритмом ?!!!!!
В этом смысле интересно предположить, что раз природа при конструировании
мозга как вычислительной системы все же прибегла к распараллеливанию
(что я думаю дорогое удовольствие даже для нее), то это значит имело
смысл. То есть "программа" интеллекта не настолько уж и сложна ( во всяком
случае там нет чего-то типа задачи о комивояджерах или определения
n-значного простого числа)
:))
И последнее, коль мы затронули скорость вычислений. Именно со скоростью
вычислений связан теперешний бум на несуществующие пока квантовые
компьютеры. И у меня есть подозрение, что на этой конференции наверняка
найдется пара сторонников очень модной нынче идеи что наш мозг -квантовый
компьютер.
Несмотря на вопли специалистов (математиков и физиков) по поводу того что
это чушь собачья, что квантовый компьютер ощутимых размеров это тонкое
состояние материи, условия для для получения которого в биологической
системе нет и быть не может, народ все равно толпами записывается в
клуб сторонников идеи что его душа -это квантовая система.
Показательно что считать результаты вычисления квантового компьютера
можно только разрушив квантовую системую. Это каким то недосягаемым
здравому смыслу образом подтверждает массовую идею о уникальности
чтьей-либо души.
Я думаю это связано с тем, что чего-то такого ждали давно и достаточно
было малейшей искры, что бы разжечь уже подготовленную фантазию.
Квантовый компьютер это устройство, которое благодаря особенности квантовых
систем может решать некоторые ТЕОРЕТИЧЕСКИ разрешимые задачи, но
НЕРАЗРЕШИМЫЕ практически из за экспоненциальной зависимости времени
их счета при росте входа.
При этом вероятностный результат работы квантового алгоритма ( как
и просто вероятностных алгоритмов) является просто расплатой за мощности
или издержками квантовой природы самого вычислителя.То есть в квантовом
компьютере случайность - помеха, досадная нагрузка.
Идея же квантовой души состоит в том что душа по-прежнему остается просто
некоторой ПРОГРАММОЙ с исходными данными но программой квантовой,
то есть такой, что простой вычислитель (и нейронная сеть тоже) не могут
вычислить то же самое что и эта "программа" в разумное время.
Хочу в связи с этим отметить.
Наш спор со Снарским касается исключительно ТЕОРЕТИЧЕСКОЙ невозможности
существования того или иного алгоритма. Поэтому нейросети или квантовый
компьютер сами по себе ничего не меняют в нашей битве.
:)))
А .Семенов
Built by Text2Html