Меню Главная Случайная статья Настройки Трансвычислительная задача Материал из https://ru.wikipedia.org Трансвычислительная задача (англ. Transcomputational problem) — в теории сложности вычислений задача, для решения которой требуется обработка более чем 1093 бит информации[1]. Число 1093, представляет собой общее число бит, обрабатываемых гипотетическим компьютером массой с Землю, работающим с максимально возможной скоростью («Предел Бремерманна»), за период времени, равный общему времени существования Земли[1][2]. Термин «трансвычислительность» был предложен Бремерманном[3]. Содержание 1 Примеры трансвычислительных проблем 1.1 Задача коммивояжёра 1.2 Тестирование интегральных схем 1.3 Распознавание узоров 1.4 Проблема анализа систем 2 Следствия 3 В научной фантастике 4 См. также 5 Примечания Примеры трансвычислительных проблем Задача коммивояжёра Задача коммивояжёра заключается в поиске пути обхода заданного списка городов, имеющего минимальную стоимость. Путь обхода должен посещать все города ровно по одному разу и возвращаться в исходный город. Если в списке n городов, то число возможных путей обхода равно . Поскольку 66! примерно равно 5,4434493911092, а 67! 3,6471110921094, задача проверки всех возможных путей становится трансвычислительной для Тестирование интегральных схем Полное тестирование всех комбинаций интегральной схемы с 308 входами и 1 выходом требует проверки 2308 комбинаций входных данных. Поскольку число 2308 является трансвычислительным, задача тестирования такой системы интегральных схем является трансвычислительной проблемой. Это означает, что отсутствует способ проверки схемы для всех входных данных методом грубой силы[1][4]. Распознавание узоров Рассмотрим массив размером Данная задача имеет отношение к изучению физиологии сетчатки. Сетчатка состоит примерно из миллиона светочувствительных клеток. Даже если у клетки имеется всего 2 возможных состояния, обработка состояния сетчатки в целом требует обработки более чем 10300 000 бит информации. Это намного превосходит предел Бремерманна[1]. Проблема анализа систем Система из k 2 3 4 5 6 7 8 9 10 n 308 194 154 133 119 110 102 97 93 Следствия Существование реальных трансвычислительных задач имеет своим следствием ограниченность компьютеров как средств обработки данных. Простым наращиванием вычислительных мощностей не удастся решить проблемы, требующие обработки огромного числа возможных ситуаций[2]. В научной фантастике В книге Дугласа Адамса «Автостопом по Галактике» была решена трансвычислительная задача, отвечающая на «Главный вопрос жизни, вселенной и всего такого» (ответ, как известно, 42). См. также Мозг-матрёшка — теоретическая вычислительная мегаструктура, имеющая размеры, сопоставимые с размером планетной системы. Предел Бремерманна Пределы вычислений Квантовые вычисления Примечания 1 2 3 4 5 6 Klir, George J. Facets of systems science (неопр.). — Springer[англ.], 1991. — С. 121—128. — ISBN 9780306439599. 1 2 Bremermann, H.J. (1962) Optimization through evolution and recombination Архивная копия от 18 декабря 2019 на Wayback Machine In: Self-Organizing systems 1962, edited M.C. Yovitts et al., Spartan Books, Washington, D.C. pp. 93-106. Heinz Muhlenbein. Algorithms, data and hypotheses : Learning in open worlds  (неопр.). German National Research Center for Computer Science. Дата обращения: 3 мая 2011. Архивировано 8 сентября 2012 года. Miles, William. Bremermann's Limit  (неопр.). Дата обращения: 1 мая 2011. Архивировано 8 сентября 2012 года.