Трансвычисли́тельная зада́ча ( англ. Transcomputational problem ) — в теории сложности вычислений задача, для решения которой требуется обработка более чем 10 ⁹³ бит информации . Число 10 ⁹³ , представляет собой общее число бит , обрабатываемых гипотетическим компьютером массой с Землю , работающим с максимально возможной скоростью (« Предел Бремерманна »), за период времени, равный общему времени существования Земли . Термин «трансвычислительность» был предложен Бремерманном .

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

Задача коммивояжёра

Задача коммивояжёра заключается в поиске пути обхода заданного списка городов, имеющего минимальную стоимость. Путь обхода должен посещать все города ровно по одному разу и возвращаться в исходный город. Если в списке n городов, то число возможных путей обхода равно n ! . Поскольку 66! примерно равно 5,443449391×10 ⁹² , а 67! ≈ 3,647111092×10 ⁹⁴ , задача проверки всех возможных путей становится трансвычислительной для n > 66 .

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

Полное тестирование всех комбинаций интегральной схемы с 308 входами и 1 выходом требует проверки 2 ³⁰⁸ комбинаций входных данных. Поскольку число 2 ³⁰⁸ является трансвычислительным, задача тестирования такой системы интегральных схем является трансвычислительной проблемой. Это означает, что отсутствует способ проверки схемы для всех входных данных методом грубой силы .

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

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

Данная задача имеет отношение к изучению физиологии сетчатки . Сетчатка состоит примерно из миллиона светочувствительных клеток. Даже если у клетки имеется всего 2 возможных состояния, обработка состояния сетчатки в целом требует обработки более чем 10 ^{300 000} бит информации. Это намного превосходит предел Бремерманна .

Проблема анализа систем

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

Следствия

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

В научной фантастике

В книге Дугласа Адамса « Автостопом по Галактике » была решена трансвычислительная задача, отвечающая на «Главный вопрос жизни, вселенной и всего такого» (ответ, как известно, 42 ).

См. также

• Мозг-матрёшка — теоретическая вычислительная мегаструктура , имеющая размеры, сопоставимые с размером планетной системы.
• Предел Бремерманна
• Пределы вычислений
• Квантовые вычисления

Примечания