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

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

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

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

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

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

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

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

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