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

В теории вычислительной сложности, транвычислительная проблема - это проблема, которая требует обработки более 10 бит информации. Любое число больше 10 называется трансвычислительным числом . Число 10, называемое пределом Бремерманна, согласно Гансу-Иоахиму Бремерманну, представляет собой общее количество битов, обрабатываемых гипотетическим компьютером размером Земля в течение периода времени, равного предполагаемому возрасту Земли. Термин «транскомпьютерные» был придуман Бремерманом.

• 1 Примеры
  • 1.1 Тестирование интегральных схем
  • 1.2 Распознавание образов
  • 1.3 Общие системные проблемы
• 2 Значение
• 3 См. Также
• 4 Ссылки

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

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

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

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

Это имеет некоторое значение для физиологических исследований сетчатки. Сетчатка содержит около миллиона светочувствительных ячеек. Даже если было только два возможных состояния для каждой ячейки (например, активное состояние и неактивное состояние), обработка retina в целом требует обработки более 10 бит информации. Это далеко за пределами предела Бремермана.

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

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

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

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

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

• Гиперзадача
• Матрешка, теоретическая вычислительная мегаструктура
• Строгий конечность