Напишите максимально длинный цикл - PullRequest
3 голосов
/ 23 декабря 2010

Недавно мне задали этот вопрос в технической дискуссии. Какой самый длинный цикл может быть записан в вычислительной науке, учитывая машину / архитектуру, на которой он должен работать? Этот цикл должен быть максимально длинным, но не бесконечным, и не должен приводить к сбою программы (рекурсия и т. Д.) Честно говоря, я не знал, как решить эту проблему, поэтому я спросил его, возможно ли это на практике. Он сказал, что, используя некоторые концепции информатики, вы можете прийти к гипотетическому числу, которое может быть непрактичным, но тем не менее оно не будет бесконечным. Кто-нибудь здесь; умеет анализировать / атаковать эту проблему.

P.S. Выбор некоторого наивысшего предела для типа, который может хранить наибольшее числовое значение, очевидно, не является ответом.

Заранее спасибо,

Ответы [ 5 ]

10 голосов
/ 23 декабря 2010

Вы попали в область машин Тьюринга.

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

так что это зависит от возможных состояний машин, которые вы могли бы наивно перевести как "его таран".

поэтому вопрос теперь таков: какой самый длинный цикл на машине может быть в нескольких состояниях X? и википедия дает ответ

6 голосов
/ 23 декабря 2010

Пожалуйста, ознакомьтесь с проблемой Busy Beaver.

http://en.wikipedia.org/wiki/Busy_beaver

1 голос
/ 23 декабря 2010

Если мы говорим об ограничении языка, то некоторые языки определяют целые числа произвольной точности (например, Python и Common Lisp), так что вы можете сосчитать до любого числа, которое вам нравится, насколько это возможно. Вы можете легко установить его слишком большим для любой реальной машины, но это не ограничение языка.

Что касается реальных машин, то это вопрос количества возможных состояний. Для каждого бита, который вы можете выделить в качестве счетчика (и он не обязательно должен быть одним элементом данных, поскольку очень легко создать счетчик произвольной длины), это два состояния, поэтому, если у вас доступно 8 ГБ памяти, вы можете считать с чем-то вроде 2 ^ 8G. Конечно, вы можете использовать файловую систему для большего количества счетчиков.

Или, предполагая, что вы не используете физически обратимые вычисления, вы можете проверить минимальную энергию, необходимую для того, чтобы немного перевернуть, поделить количество доступной энергии (например, на общую ожидаемую солнечную мощность или что-то еще) и получить предел. 1005 *

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

Слишком много возможных ответов, чтобы дать один.

1 голос
/ 23 декабря 2010

Наибольшее возможное конечное значение? Как математик, я нахожу это смешным. Возможно, проблему можно объяснить лучше.

0 голосов
/ 23 декабря 2010

Если «длинный» означает время, хорошая конечная петля должна быть хорошей ставкой:

for(unsigned long long i = 0; i < ULONG_LONG_MAX; ++i) sleep(UINT_MAX);

Хорошо, этот ответ не очень серьезен, но на самом деле я считаю, что вопрос совершенно бесполезенна собеседовании.Зачем?Согласно ответу С. Лотта, речь может идти о проблеме Занятого бобра, которой почти 50 лет, и она совершенно неизвестна, потому что никто не может использовать ее на реальной работе.

...