Транвычислительная проблема - Transcomputational problem

В теория сложности вычислений, а транвычислительная проблема проблема, требующая обработки более 1093 биты информации.[1] Любое число больше 1093 называется транвычислительный номер. Число 1093, называется Предел Бремермана, согласно Ханс-Иоахим Бремерманн, общее количество бит, обрабатываемых гипотетическим компьютером размером земной шар в течение периода времени, равного предполагаемому возрасту Земли.[1][2] Период, термин транскомпьютерный был придуман Бремерманом.[3]

Примеры

Тестирование интегральных схем

Исчерпывающее тестирование всех комбинаций Интегральная схема с 309 входы и 1 выход требует тестирования в общей сложности 2309 комбинации входов. Поскольку число 2309 транскомпьютерное число (то есть число больше 1093), проблема тестирования такой системы интегральные схемы это транскомпьютерная проблема. Это означает, что невозможно проверить правильность схемы для всех комбинаций входов через грубая сила один.[1][4]

Распознавание образов

Рассмотрим q×q массив шахматная доска типа, каждый квадрат которого может иметь одно из k цвета. Всего есть kп цвет узоры, куда п = q2. Задача определения наилучшей классификации узоров по какому-либо выбранному критерию может быть решена путем перебора всех возможных цветовых узоров. Для двух цветов такой поиск становится трансвычислительным, если размер массива 18 × 18 или больше. Для массива 10 × 10 проблема становится межвычислительной, когда имеется 9 или более цветов.[1]

Это имеет некоторое отношение к физиологическим исследованиям сетчатка. Сетчатка содержит около миллиона светочувствительный клетки. Даже если бы для каждой ячейки было только два возможных состояния (например, активное состояние и неактивное состояние), обработка сетчатка в целом требует обработки более 10300,000 биты информации. Это далеко за пределами Предел Бремермана.[1]

Общие системные проблемы

А система из п переменные, каждая из которых может принимать k разные состояния, могут иметь kп возможные состояния системы. Для анализа такой системы требуется минимум kп биты информации подлежат обработке. Проблема становится межвычислительной, когда kп > 1093. Это происходит для следующих значений k и п:[1]

k2345678910
п3081941541331191101029793

Подразумеваемое

Существование реальных транвычислительных проблем подразумевает ограничения компьютеров как инструментов обработки данных. Этот момент лучше всего резюмируется собственными словами Бремерманна:[2]

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

Смотрите также

Рекомендации

  1. ^ а б c d е ж Клир, Джордж Дж. (1991). Грани системной науки. Springer. С. 121–128. ISBN  978-0-306-43959-9.
  2. ^ а б Бремерманн, Х.Дж. (1962) Оптимизация через эволюцию и рекомбинацию В: Самоорганизующиеся системы 1962 г., под редакцией М.К. Йовитц и др., Spartan Books, Вашингтон, округ Колумбия, стр. 93–106.
  3. ^ Хайнц Мюленбейн. «Алгоритмы, данные и гипотезы: обучение в открытых мирах» (PDF). Немецкий национальный исследовательский центр компьютерных наук. Получено 3 мая 2011.
  4. ^ Майлз, Уильям. «Предел Бремермана». Получено 1 мая 2011. Хотя источник использует 308 как количество входов, это число основано на ошибке: 2308 < 1093.