Здравствуйте, FR, Вы писали:
FR>Здравствуйте, GhostCoders, Вы писали:
GC>>понимаете, тут какое дело. В реальной программе, мы будем использовать тот же float, GC>>который имеет 32-бита, и имеет ограничение на число знаков после запятой.
FR>
FR>Python 2.5.1 (r251:54863, Apr 18 2007, 08:51:08) [MSC v.1310 32 bit (Intel)] on
FR>win32
FR>Type "help", "copyright", "credits" or "license" for more information.
>>>> 123 ** 123
FR>11437436793461719009988029522806627674621807845185022977588797505236950478566689
FR>64466065683652015421696499747277306288423453431965811348959199428208744498372120
FR>99476648958359023796078549041949007807220625356526926729664064846685758382803707
FR>100766740220839267L
FR>
Число большое, да, это правда, больше чем float. Но питон все равно имеет ограничение в размере ОЗУ,
например, не умеет обрабатывать числа, которые занимают памяти больше чем все ОЗУ компьютера (и жесткого диска).
Третий Рим должен пасть!
Re[7]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для GC>вычисления следующего.
Как я уже говорил, пользователь может вводить каждое новое число с клавиатуры, не в этом дело
Вот пример на C++ (написан на скорую руку, упрощённый; на самом деле, буфер там не к месту — можно было обойтись и без него):
// Получение следующего числа в дробной части "пи" (чёрный ящик):char getNextNumberInPi () {
char digit = 0;
for ( ;; ) {
std::cin >> digit;
if ( std::isdigit ( digit ) ) {
return digit;
}
std::cout << "Retype! No digit in input." << std::endl;
}
}
// Необходимая последовательность и её длина:char const needSequence[] = "8432741183478374439008753924";
std::size_t const needLength = std::strlen ( needSequence );
int main () {
// Можно было сделать проще и без буфера:
std::vector<char> buffer;
for ( ;; ) {
// Новое число в конец буфера:
buffer.push_back ( getNextNumberInPi () );
// Если нет точного совпадения - очищаем буфер:if ( !std::equal ( buffer.begin (), buffer.end (), needSequence ) ) {
buffer.clear ();
}
// Если совпадение есть и буфер достиг нужного размера - останавливаемся:else if ( buffer.size () == needLength ) {
std::cout << "Stopped!" << std::endl;
return 0;
}
}
}
Re[4]: Реализован простейший язык для тестирования на зацик
Здравствуйте, 0K, Вы писали:
0K>Здравствуйте, GhostCoders, Вы писали:
GC>>понимаете, тут какое дело. В реальной программе, мы будем использовать тот же float, GC>>который имеет 32-бита, и имеет ограничение на число знаков после запятой.
0K>А если будем использовать массив байт? Причем массив может иметь неограниченный размер. Найдет алгоритм все значения массива, при которых функция зациклится.
Неправда. Массивы в наших компьютерах всегда имееют ограниченный размер. Например, на 32-разрядной ОС
массив не может быть больше 4G.
GC>>Мой анализатор проверит это дело, то только до того знака, до которого позволяет float.
0K>Насколько быстрее чем методом простого перебора, к примеру?
GC>>По хорошему, мы должны использовать переменную с бесконечным числом бит, но GC>>у нас никогда не будет компьютера с бесконечной памятью. Машина Тьюринга, имеет бесконечную память.
0K>А если не бесконечное чило бит а просто очень большое? Определить зацикливание не сложно... Видимо все дело в скорости... Насколько быстр ваш алгоритм?
"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?
Все таки можно определить зацикливание?
Третий Рим должен пасть!
Re[8]: Реализован простейший язык для тестирования на зацик
Здравствуйте, Alexey F, Вы писали:
AF>Здравствуйте, GhostCoders, Вы писали:
GC>>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для GC>>вычисления следующего.
AF>Как я уже говорил, пользователь может вводить каждое новое число с клавиатуры, не в этом дело AF>Вот пример на C++ (написан на скорую руку, упрощённый; на самом деле, буфер там не к месту — можно было обойтись и без него): AF>
AF>// Получение следующего числа в дробной части "пи" (чёрный ящик):
AF>char getNextNumberInPi () {
AF> char digit = 0;
AF> for ( ;; ) {
AF> std::cin >> digit;
AF> if ( std::isdigit ( digit ) ) {
AF> return digit;
AF> }
AF> std::cout << "Retype! No digit in input." << std::endl;
AF> }
AF>}
AF>// Необходимая последовательность и её длина:
AF>char const needSequence[] = "8432741183478374439008753924";
AF>std::size_t const needLength = std::strlen ( needSequence );
AF>int main () {
AF> // Можно было сделать проще и без буфера:
AF> std::vector<char> buffer;
AF> for ( ;; ) {
AF> // Новое число в конец буфера:
AF> buffer.push_back ( getNextNumberInPi () );
AF> // Если нет точного совпадения - очищаем буфер:
AF> if ( !std::equal ( buffer.begin (), buffer.end (), needSequence ) ) {
AF> buffer.clear ();
AF> }
AF> // Если совпадение есть и буфер достиг нужного размера - останавливаемся:
AF> else if ( buffer.size () == needLength ) {
AF> std::cout << "Stopped!" << std::endl;
AF> return 0;
AF> }
AF> }
AF>}
AF>
Вы сами понимаете что ввод пользователя привносит новую информацию в программу. Пользователь находится вне вычислительной системы, и предугадать его поведение не возможно.
Идет речь о "закрытых" участках кода, в которые информация из внешнего мира не поступает,
а только обрабатываются.
Третий Рим должен пасть!
Re[5]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>Число большое, да, это правда, больше чем float. Но питон все равно имеет ограничение в размере ОЗУ, GC>например, не умеет обрабатывать числа, которые занимают памяти больше чем все ОЗУ компьютера (и жесткого диска).
Твой алгоритм явно нелинейный, так что будем ждать для любого нетривиального кода миллард-другой лет?
Re[7]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для GC>вычисления следующего.
Про пи не знаю но тот же Аттрактор Лоренца не требует дополнительной памяти и при этом псевдослучаен. Да и теже детерминированные фракталы тоже можно вычислять на ограниченой памяти.
Re[5]: Реализован простейший язык для тестирования на зацик
От:
Аноним
Дата:
01.03.09 12:04
Оценка:
Здравствуйте, GhostCoders, Вы писали:
GC>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав? GC>Все таки можно определить зацикливание?
Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?
А говорят еще индусы злодеи. Хотя кто знает, может под ником GhostCoders какой-нибудь Брахмапутра тут решил над народом поиздеваться
Re[8]: Реализован простейший язык для тестирования на зацик
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, GhostCoders, Вы писали:
GC>>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для GC>>вычисления следующего.
FR>Про пи не знаю но тот же Аттрактор Лоренца не требует дополнительной памяти и при этом псевдослучаен. Да и теже детерминированные фракталы тоже можно вычислять на ограниченой памяти.
Только ПСЕВдослучаен.
Третий Рим должен пасть!
Re[2]: Реализован простейший язык для тестирования на зацик
Здравствуйте, PolyTech, Вы писали:
PT>Здравствуйте, GhostCoders, Вы писали:
GC>>Реализовал транслятор простейшего языка программирования.
PT>Мне почему-то сразу вот это напомнило: PT>http://www.rus-os.narod.ru
Никакой это не вечный двигатель. Вы просто некомпетентны в этом вопросе.
Не знаете простых вещей
в разделе "Common pitfalls" (Распространенные заблуждения)
указывается что проблема останова РАЗРЕШИМА для машин с конечным набором состояний.
Машина Тьюринга является машиной с бесконечным числом состояний.
То есть не я первый это придумал. А придумал это Minsky в 1967 году.
Так что АНАЛИЗАТОР теоритически возможен, а на практике будет иметь существенные огранияения, это, да, правда,
с этим согласен.
Русская wikki все-таки является неполной по сравнению с английской.
Третий Рим должен пасть!
Re[6]: Реализован простейший язык для тестирования на зацик
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, GhostCoders, Вы писали:
GC>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав? GC>>Все таки можно определить зацикливание?
А>Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?
В этом случае время работы конечно, и АНАЛИЗАТОР возможен
Третий Рим должен пасть!
Re[7]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, GhostCoders, Вы писали:
GC>>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав? GC>>>Все таки можно определить зацикливание?
А>>Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?
GC>В этом случае время работы конечно, и АНАЛИЗАТОР возможен
Вон из профессии.
Re[5]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
0K>>А если не бесконечное чило бит а просто очень большое? Определить зацикливание не сложно... Видимо все дело в скорости... Насколько быстр ваш алгоритм?
GC>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав? GC>Все таки можно определить зацикливание?
Конечно можно. Запустить и подождать 1 * 10^n лет. Если получен ответ -- значит не зациклился.
Ценность в том, чтобы определить это с определенной скоростью. Для простых случаев, типа деления на нуль, это сделать не сложно. Есть ли универсальный способ для всех алгоритмов (кроме как запустить и подождать пару мильярдов лет)? Видимо об этом Тьюринг и говорил...
Насколько ваш алгоритм быстрее простого ожидания возврата из цикла?
Re[7]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для GC>вычисления следующего.
Да. Такие алгоритмы есть для десятичной и двоичной баз (и для ряда других).
Sapienti sat!
Re[9]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
FR>>Про пи не знаю но тот же Аттрактор Лоренца не требует дополнительной памяти и при этом псевдослучаен. Да и теже детерминированные фракталы тоже можно вычислять на ограниченой памяти.
GC>Только ПСЕВдослучаен.
Угу, только есть пробема чтобы узнать эту псевдослучайную последовательность ее надо вычислять, а сходимость в заисимости от начальных условий, на современых машинах, у тех же аттракторов может быть от долей секунд до миллиардов лет.
Re[8]: Реализован простейший язык для тестирования на зацик
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, GhostCoders, Вы писали:
GC>>Здравствуйте, Аноним, Вы писали:
А>>>Здравствуйте, GhostCoders, Вы писали:
GC>>>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав? GC>>>>Все таки можно определить зацикливание?
А>>>Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?
GC>>В этом случае время работы конечно, и АНАЛИЗАТОР возможен
А>Вон из профессии.
Сам пшел вон.
Учи компьютерную азбуку. А наверное бывший ветеринар программирует тут.
Третий Рим должен пасть!
Re[6]: Реализован простейший язык для тестирования на зацик
Здравствуйте, 0K, Вы писали:
0K>Здравствуйте, GhostCoders, Вы писали:
0K>>>А если не бесконечное чило бит а просто очень большое? Определить зацикливание не сложно... Видимо все дело в скорости... Насколько быстр ваш алгоритм?
GC>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав? GC>>Все таки можно определить зацикливание?
0K>Конечно можно. Запустить и подождать 1 * 10^n лет. Если получен ответ -- значит не зациклился.
Нет, определить что алгоритм зациклился можно и намного раньше.
Вы просто некомпетентны в этом вопросе.
Не знаете простых вещей
в разделе "Common pitfalls" (Распространенные заблуждения)
указывается что проблема останова РАЗРЕШИМА для машин с конечным набором состояний.
Машина Тьюринга является машиной с бесконечным числом состояний.
То есть не я первый это придумал. А придумал это Minsky в 1967 году.
Так что АНАЛИЗАТОР теоритически возможен, а на практике будет иметь существенные огранияения, это, да, правда,
с этим согласен.
Русская wikki все-таки является неполной по сравнению с английской.
0K>Ценность в том, чтобы определить это с определенной скоростью. Для простых случаев, типа деления на нуль, это сделать не сложно. Есть ли универсальный способ для всех алгоритмов (кроме как запустить и подождать пару мильярдов лет)? Видимо об этом Тьюринг и говорил...
Нет, Тьюринг говорил об другом. Он говорил, что вообще невозможно построить АНАЛИЗАТОР в принципе (для машины Тьюринга).
На практике (я имею в виду разумные ограничения по времени) можно использовать приемы "разделяй и властвуй" и подобные.
Третий Рим должен пасть!
Re[3]: Реализован простейший язык для тестирования на зацик
Здравствуйте, GhostCoders, Вы писали:
GC>в разделе "Common pitfalls" (Распространенные заблуждения) GC>указывается что проблема останова РАЗРЕШИМА для машин с конечным набором состояний. GC>Машина Тьюринга является машиной с бесконечным числом состояний. GC>То есть не я первый это придумал. А придумал это Minsky в 1967 году.
Любые реальные компьютеры — это не машины Тьюринга, а конечные автоматы. Так что, теоретически, мы можем просто перебрать все их возможные состояния. Их количество ограничено так называемым числом "Busy beaver" (http://en.wikipedia.org/wiki/Busy_Beaver).
Вот только это число растёт просто НЕВООБРАЗИМО быстро. Для машины Тьюринга с лентой из 6 элементов _нижняя_ граница составляет 10^1439 шагов (другой автор цитирует 4096 ^^ 166).
Причём не существует общих способов анализа проблемы останова для алгоритма, работающих за меньшее число шагов, чем сам алгоритм. Т.е. тебе для анализа вполне вероятно может потребоваться выполнить эти 10^1439 шагов.
Так что любой общий алгоритм анализа — это изобретение вечного двигателя.
Sapienti sat!
Re[6]: Реализован простейший язык для тестирования на зацик
Здравствуйте, 0K, Вы писали:
0K> Есть ли универсальный способ для всех алгоритмов (кроме как запустить и подождать пару мильярдов лет)? Видимо об этом Тьюринг и говорил...
Боюсь, что пары миллиардов лет может нехватить. Насколько я помню, доказано, что невозможно построить машину тьюринга которая гарантированно определяет завершит любая другая машина тьюринга когда-либо работу или нет.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, GhostCoders, Вы писали:
GC>>в разделе "Common pitfalls" (Распространенные заблуждения) GC>>указывается что проблема останова РАЗРЕШИМА для машин с конечным набором состояний. GC>>Машина Тьюринга является машиной с бесконечным числом состояний. GC>>То есть не я первый это придумал. А придумал это Minsky в 1967 году. C>Любые реальные компьютеры — это не машины Тьюринга, а конечные автоматы. Так что, теоретически, мы можем просто перебрать все их возможные состояния. Их количество ограничено так называемым числом "Busy beaver" (http://en.wikipedia.org/wiki/Busy_Beaver).
C>Вот только это число растёт просто НЕВООБРАЗИМО быстро. Для машины Тьюринга с лентой из 6 элементов _нижняя_ граница составляет 10^1439 шагов (другой автор цитирует 4096 ^^ 166).
Это зависит от числа возможных состояний головки машины Тьюринга. Чем оно больше тем больше шагов.
C>Причём не существует общих способов анализа проблемы останова для алгоритма, работающих за меньшее число шагов, чем сам алгоритм. Т.е. тебе для анализа вполне вероятно может потребоваться выполнить эти 10^1439 шагов.
А за большее число шагов или за равное — существуют такие алгоритмы.
C>Так что любой общий алгоритм анализа — это изобретение вечного двигателя.
Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?