Re[4]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 11:40
Оценка:
Здравствуйте, 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]: Реализован простейший язык для тестирования на зацик
От: Alexey F  
Дата: 01.03.09 11:41
Оценка:
Здравствуйте, 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]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 11:44
Оценка:
Здравствуйте, 0K, Вы писали:

0K>Здравствуйте, GhostCoders, Вы писали:


GC>>понимаете, тут какое дело. В реальной программе, мы будем использовать тот же float,

GC>>который имеет 32-бита, и имеет ограничение на число знаков после запятой.

0K>А если будем использовать массив байт? Причем массив может иметь неограниченный размер. Найдет алгоритм все значения массива, при которых функция зациклится.


Неправда. Массивы в наших компьютерах всегда имееют ограниченный размер. Например, на 32-разрядной ОС
массив не может быть больше 4G.

GC>>Мой анализатор проверит это дело, то только до того знака, до которого позволяет float.


0K>Насколько быстрее чем методом простого перебора, к примеру?


GC>>По хорошему, мы должны использовать переменную с бесконечным числом бит, но

GC>>у нас никогда не будет компьютера с бесконечной памятью. Машина Тьюринга, имеет бесконечную память.

0K>А если не бесконечное чило бит а просто очень большое? Определить зацикливание не сложно... Видимо все дело в скорости... Насколько быстр ваш алгоритм?


"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?
Все таки можно определить зацикливание?
Третий Рим должен пасть!
Re[8]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 11:51
Оценка:
Здравствуйте, 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]: Реализован простейший язык для тестирования на зацик
От: FR  
Дата: 01.03.09 11:59
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>Число большое, да, это правда, больше чем float. Но питон все равно имеет ограничение в размере ОЗУ,

GC>например, не умеет обрабатывать числа, которые занимают памяти больше чем все ОЗУ компьютера (и жесткого диска).

Твой алгоритм явно нелинейный, так что будем ждать для любого нетривиального кода миллард-другой лет?
Re[7]: Реализован простейший язык для тестирования на зацик
От: FR  
Дата: 01.03.09 12:01
Оценка: +1
Здравствуйте, GhostCoders, Вы писали:

GC>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для

GC>вычисления следующего.

Про пи не знаю но тот же Аттрактор Лоренца не требует дополнительной памяти и при этом псевдослучаен. Да и теже детерминированные фракталы тоже можно вычислять на ограниченой памяти.
Re[5]: Реализован простейший язык для тестирования на зацик
От: Аноним  
Дата: 01.03.09 12:04
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?

GC>Все таки можно определить зацикливание?

Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?

А говорят еще индусы злодеи. Хотя кто знает, может под ником GhostCoders какой-нибудь Брахмапутра тут решил над народом поиздеваться
Re[8]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 12:07
Оценка:
Здравствуйте, FR, Вы писали:

FR>Здравствуйте, GhostCoders, Вы писали:


GC>>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для

GC>>вычисления следующего.

FR>Про пи не знаю но тот же Аттрактор Лоренца не требует дополнительной памяти и при этом псевдослучаен. Да и теже детерминированные фракталы тоже можно вычислять на ограниченой памяти.


Только ПСЕВдослучаен.
Третий Рим должен пасть!
Re[2]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 12:09
Оценка:
Здравствуйте, PolyTech, Вы писали:

PT>Здравствуйте, GhostCoders, Вы писали:


GC>>Реализовал транслятор простейшего языка программирования.


PT>Мне почему-то сразу вот это напомнило:

PT>http://www.rus-os.narod.ru


Никакой это не вечный двигатель. Вы просто некомпетентны в этом вопросе.
Не знаете простых вещей

Например здесь
http://en.wikipedia.org/wiki/Halting_problem

в разделе "Common pitfalls" (Распространенные заблуждения)
указывается что проблема останова РАЗРЕШИМА для машин с конечным набором состояний.
Машина Тьюринга является машиной с бесконечным числом состояний.
То есть не я первый это придумал. А придумал это Minsky в 1967 году.

Так что АНАЛИЗАТОР теоритически возможен, а на практике будет иметь существенные огранияения, это, да, правда,
с этим согласен.

Русская wikki все-таки является неполной по сравнению с английской.
Третий Рим должен пасть!
Re[6]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 12:10
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, GhostCoders, Вы писали:


GC>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?

GC>>Все таки можно определить зацикливание?

А>Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?


В этом случае время работы конечно, и АНАЛИЗАТОР возможен
Третий Рим должен пасть!
Re[7]: Реализован простейший язык для тестирования на зацик
От: Аноним  
Дата: 01.03.09 12:13
Оценка: +1 -1
Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, Аноним, Вы писали:


А>>Здравствуйте, GhostCoders, Вы писали:


GC>>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?

GC>>>Все таки можно определить зацикливание?

А>>Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?


GC>В этом случае время работы конечно, и АНАЛИЗАТОР возможен


Вон из профессии.
Re[5]: Реализован простейший язык для тестирования на зацик
От: 0K Ниоткуда  
Дата: 01.03.09 12:13
Оценка: +1
Здравствуйте, GhostCoders, Вы писали:

0K>>А если не бесконечное чило бит а просто очень большое? Определить зацикливание не сложно... Видимо все дело в скорости... Насколько быстр ваш алгоритм?


GC>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?

GC>Все таки можно определить зацикливание?

Конечно можно. Запустить и подождать 1 * 10^n лет. Если получен ответ -- значит не зациклился.

Ценность в том, чтобы определить это с определенной скоростью. Для простых случаев, типа деления на нуль, это сделать не сложно. Есть ли универсальный способ для всех алгоритмов (кроме как запустить и подождать пару мильярдов лет)? Видимо об этом Тьюринг и говорил...

Насколько ваш алгоритм быстрее простого ожидания возврата из цикла?
Re[7]: Реализован простейший язык для тестирования на зацик
От: Cyberax Марс  
Дата: 01.03.09 12:19
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>Вопрос в том существует ли алгоритм нахождения числа "пи", который не использует предыдущие числа для

GC>вычисления следующего.
Да. Такие алгоритмы есть для десятичной и двоичной баз (и для ряда других).
Sapienti sat!
Re[9]: Реализован простейший язык для тестирования на зацик
От: FR  
Дата: 01.03.09 12:21
Оценка:
Здравствуйте, GhostCoders, Вы писали:

FR>>Про пи не знаю но тот же Аттрактор Лоренца не требует дополнительной памяти и при этом псевдослучаен. Да и теже детерминированные фракталы тоже можно вычислять на ограниченой памяти.


GC>Только ПСЕВдослучаен.


Угу, только есть пробема чтобы узнать эту псевдослучайную последовательность ее надо вычислять, а сходимость в заисимости от начальных условий, на современых машинах, у тех же аттракторов может быть от долей секунд до миллиардов лет.
Re[8]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 12:23
Оценка: -2
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, GhostCoders, Вы писали:


GC>>Здравствуйте, Аноним, Вы писали:


А>>>Здравствуйте, GhostCoders, Вы писали:


GC>>>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?

GC>>>>Все таки можно определить зацикливание?

А>>>Определим понятие "возможности" как "анализатору в худшем случае требуется меньше 10 лет чтобы выдать результат на самом производительном суперкомпьютере из существующих". Так понятнее?


GC>>В этом случае время работы конечно, и АНАЛИЗАТОР возможен


А>Вон из профессии.


Сам пшел вон.

Учи компьютерную азбуку. А наверное бывший ветеринар программирует тут.
Третий Рим должен пасть!
Re[6]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 12:23
Оценка:
Здравствуйте, 0K, Вы писали:

0K>Здравствуйте, GhostCoders, Вы писали:


0K>>>А если не бесконечное чило бит а просто очень большое? Определить зацикливание не сложно... Видимо все дело в скорости... Насколько быстр ваш алгоритм?


GC>>"Определить зацикливание не сложно... " — то есть Вы утверждаете что Тьюринг не прав?

GC>>Все таки можно определить зацикливание?

0K>Конечно можно. Запустить и подождать 1 * 10^n лет. Если получен ответ -- значит не зациклился.


Нет, определить что алгоритм зациклился можно и намного раньше.

Вы просто некомпетентны в этом вопросе.
Не знаете простых вещей

Например здесь
http://en.wikipedia.org/wiki/Halting_problem

в разделе "Common pitfalls" (Распространенные заблуждения)
указывается что проблема останова РАЗРЕШИМА для машин с конечным набором состояний.
Машина Тьюринга является машиной с бесконечным числом состояний.
То есть не я первый это придумал. А придумал это Minsky в 1967 году.

Так что АНАЛИЗАТОР теоритически возможен, а на практике будет иметь существенные огранияения, это, да, правда,
с этим согласен.

Русская wikki все-таки является неполной по сравнению с английской.

0K>Ценность в том, чтобы определить это с определенной скоростью. Для простых случаев, типа деления на нуль, это сделать не сложно. Есть ли универсальный способ для всех алгоритмов (кроме как запустить и подождать пару мильярдов лет)? Видимо об этом Тьюринг и говорил...


Нет, Тьюринг говорил об другом. Он говорил, что вообще невозможно построить АНАЛИЗАТОР в принципе (для машины Тьюринга).

На практике (я имею в виду разумные ограничения по времени) можно использовать приемы "разделяй и властвуй" и подобные.
Третий Рим должен пасть!
Re[3]: Реализован простейший язык для тестирования на зацик
От: Cyberax Марс  
Дата: 01.03.09 12:28
Оценка: 2 (1) +2
Здравствуйте, 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]: Реализован простейший язык для тестирования на зацик
От: g_i  
Дата: 01.03.09 12:29
Оценка:
Здравствуйте, 0K, Вы писали:

0K> Есть ли универсальный способ для всех алгоритмов (кроме как запустить и подождать пару мильярдов лет)? Видимо об этом Тьюринг и говорил...


Боюсь, что пары миллиардов лет может нехватить. Насколько я помню, доказано, что невозможно построить машину тьюринга которая гарантированно определяет завершит любая другая машина тьюринга когда-либо работу или нет.
Re: в КУ было...
От: Alexander G Украина  
Дата: 01.03.09 12:33
Оценка: 1 (1) +1
http://www.rsdn.ru/forum/message/3190404.1.aspx
Автор: CiViLiS
Дата: 27.11.08
Русский военный корабль идёт ко дну!
Re[4]: Реализован простейший язык для тестирования на зацик
От: GhostCoders Россия  
Дата: 01.03.09 12:34
Оценка:
Здравствуйте, 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>Так что любой общий алгоритм анализа — это изобретение вечного двигателя.

Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?
Третий Рим должен пасть!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.