Здраствуйте!

Реализовал транслятор простейшего языка программирования.
Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
и если зависает то на каких наборах данных.

Вот описание языка:
* This is specification of Simple Language *
* Copyright (c) 2009 PETR PETROV *

* This is an example of comment *

* Please note that indentifiers are case-sentensive *

* now we declares subprogram *
SUBPROGRAM someSubProgram
* now we declares that our subprogram accepts "arg1" as argument and has int8 type (like "char" type in C) *
INPUT arg1 TYPE int8
* output variable *
OUTPUT res1 TYPE int8
* temporary variables (local variables) default values are zeros *
VAR temp0 TYPE int8
VAR temp1 TYPE int8
* subprogram body begins *
BEGIN
* set "temp1" variable to "13" value *
SET temp1 13
* declare label with name *
LABEL abc
* If arg1 == temp1 then goto label abc *
IFEQUAL arg1 temp1 GOTO abc EIF
* arg1 = arg1 — 1 *
DEC arg1
* res1 = res1 + 1 *
INC res1
* res1 = res1 + 1 *
INC res1
* If arg1 == temp0 then goto label end *
IFEQUAL arg1 temp0 GOTO end EIF
* goto abc *
GOTO abc
LABEL end
END

* PROGRAM is similar to SUBPROGRAM but defines the entry point of the application *
* PROGRAM must be single in entire file *
* input variables can be entered by user *

PROGRAM ProgramA
INPUT arg1 TYPE int8
OUTPUT res1 TYPE int8
VAR localVar TYPE int8
BEGIN
CALL someSubProgram arg1 res1
END

* some features of Simple Language *
SUBPROGRAM example
INPUT arg1 TYPE int8
OUTPUT res1 TYPE int8
VAR temp0 TYPE int8
BEGIN
* set the value of variable *
SET temp0 50
* res1 = arg1 *
LET res1 arg1
* if arg1 > arg1 then goto label1 else label2 *
IFGREAT arg1 arg2 GOTO label1 ELSE label2
* if arg1 < arg1 then goto label1 else label2 *
IFLESS arg1 arg2 GOTO label1 ELSE label2
* res1 = arg1 / temp0 *
DIV res1 arg1 temp0
* res1 = arg1 & temp0 *
MOD res1 arg1 temp0
* res1 = arg1 x temp0 *
MUL res1 arg1 temp0
* res1 = arg1 + temp0 *
ADD res1 arg1 temp0
* res1 = arg1 — temp0 *
SUB res1 arg1 temp0

* calling a subprogram someSubProgram(temp0,res1) *
CALL someSubProgram temp0 res1

END

Реализовал также и сам анализатор, который определяет зацикливается ли входной алгоритм или нет.

С Уважением,
Петр

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

GC>Здраствуйте!

И вам не хворать.
Можно объяснить, каким боком эта набившая оскомину тема относится к Shareware и бизнесу?

GC>Реализовал транслятор простейшего языка программирования.
GC>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>и если зависает то на каких наборах данных.

Слушай, это случайно не твой сайт здесь ?

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

R>И вам не хворать.
R>Можно объяснить, каким боком эта набившая оскомину тема относится к Shareware и бизнесу?

Его же в философии без соли съедят

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

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

Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
http://rsdn.ru/forum/Default.aspx?mid=3307978

Автор: RomikT
Дата: 27.02.09

и узнать, наконец-то ответ!

GC>* now we declares subprogram *

Лучше бы по-русски писал, все равно это не английский.

Здравствуйте, D. Mon, Вы писали:

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

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

DM>Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
DM>http://rsdn.ru/forum/Default.aspx?mid=3307978

Автор: RomikT
Дата: 27.02.09

DM>и узнать, наконец-то ответ!

Вот пример данной функции на этом языке:

* This is function from RomikT *

PROGRAM RomikT
INPUT n TYPE int8
OUTPUT res TYPE int8
VAR value_1 TYPE int8
VAR value_2 TYPE int8
VAR value_3 TYPE int8
VAR value_0 TYPE int8
VAR temp0 TYPE int8
BEGIN
SET value_1 1
SET value_2 2
SET value_3 3
SET value_0 0
LABEL while_cycle
IFEQUAL n value_1 GOTO end EIF
MOD temp0 n value_2
IFEQUAL temp0 value_0 GOTO _even EIF
MUL n n value_3
INC n
GOTO c_cont
LABEL _even
DIV n n value_2
LABEL c_cont
GOTO while_cycle
LABEL end
LET res n
END

Вот результат работы моего анализатора (только первая часть, так как случаев с зависанием много):
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 0
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 15
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 23
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 30
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 35
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 39
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 45
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 46
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 49
HALT HAS BEEN DETECTED.
INPUT VARIABLES:
n = 53

.... и т.д.
и в конце немного "статистики".
RESULTS:
total : 256
halted: 146
passed: 110
Q = 0.570313 (то самое "магическое" омега, которое было описано здесь: http://elementy.ru/lib/430319)

Здравствуйте, Kubyshev Andrey, Вы писали:

GC>>Реализовал транслятор простейшего языка программирования.
GC>>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>>и если зависает то на каких наборах данных.

KA>Слушай, это случайно не твой сайт здесь ?
Нет, сайт не мой, но сайт моего партнера здесь http://www.pdf3d.co.uk

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

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

R>>И вам не хворать.
R>>Можно объяснить, каким боком эта набившая оскомину тема относится к Shareware и бизнесу?

FR>Его же в философии без соли съедят

Вообще можно даже этот топик и в философию перенести. Думаю что так будет обсуждение конструктивней.
Но дело в том что философия абстрактна и фантазийна, а мой метод рабочий (хотя конечно и с ограничениями).

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

GC>Здравствуйте, D. Mon, Вы писали:

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

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

DM>>Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
DM>>http://rsdn.ru/forum/Default.aspx?mid=3307978

Автор: RomikT
Дата: 27.02.09

DM>>и узнать, наконец-то ответ!

GC>Вот пример данной функции на этом языке:

GC>* This is function from RomikT *

GC>PROGRAM RomikT
GC>INPUT n TYPE int8

Как бы так помягче выразиться.. С какого перепугу N тут int8? "Анализатор" тупо перебирает все возможные значения входных параметров??

Автор, это уже не смешно. Реальная клиника.

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

GC>Реализовал транслятор простейшего языка программирования.
GC>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>и если зависает то на каких наборах данных.

Интересно получилось И так быстро!
Так что там с одним из предложенных тестовых заданиий

Автор: Alexey F
Дата: 28.02.09

:

"Если где-либо в дробной части числа "пи" встречается последовательность цифр 84327411834783744390087539249 — завершить цикл"

?
Что на это скажет анализатор?

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

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

GC>>Здравствуйте, D. Mon, Вы писали:

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

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

DM>>>Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
DM>>>http://rsdn.ru/forum/Default.aspx?mid=3307978

Автор: RomikT
Дата: 27.02.09

DM>>>и узнать, наконец-то ответ!

GC>>Вот пример данной функции на этом языке:

GC>>* This is function from RomikT *

GC>>PROGRAM RomikT
GC>>INPUT n TYPE int8

А>Как бы так помягче выразиться.. С какого перепугу N тут int8? "Анализатор" тупо перебирает все возможные значения входных параметров??

А почему бы и нет?

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

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

Мне почему-то сразу вот это напомнило:
http://www.rus-os.narod.ru

Здравствуйте, Alexey F, Вы писали:

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

GC>>Реализовал транслятор простейшего языка программирования.
GC>>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>>и если зависает то на каких наборах данных.

AF>Интересно получилось И так быстро!
AF>Так что там с одним из предложенных тестовых заданиий

Автор: Alexey F
Дата: 28.02.09

:
AF>

AF>"Если где-либо в дробной части числа "пи" встречается последовательность цифр 84327411834783744390087539249 — завершить цикл"

AF>?
AF>Что на это скажет анализатор?

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

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

Можно использовать double, точность болше, знаков после запятой тоже. Но число знаков тоже КОНЕЧНО.

По хорошему, мы должны использовать переменную с бесконечным числом бит, но
у нас никогда не будет компьютера с бесконечной памятью. Машина Тьюринга, имеет бесконечную память.

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

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

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

PT>Мне почему-то сразу вот это напомнило:
PT>http://www.rus-os.narod.ru

а мне нет

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

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

Пардон, всё же мне надо чётче формулировать свои мысли
Число "пи" было взято как пример числа, вычисление которого с бесконечной точностью занимает бесконечное время, причём мы не можем предугадать, какое число появится следующим при следующей итерации вычислений. Ближайший аналог — ГСЧ, если условиться, что генерируемые им числа не предсказуемы.
Т.е.:

// Якобы, следующее число в "пи" :)
int getNextNumberInPi () {
    return std::rand () % 10;
}

будет достаточно

Здравствуйте, Alexey F, Вы писали:

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

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

AF>Пардон, всё же мне надо чётче формулировать свои мысли
AF>Число "пи" было взято как пример числа, вычисление которого с бесконечной точностью занимает бесконечное время, причём мы не можем предугадать, какое число появится следующим при следующей итерации вычислений. Ближайший аналог — ГСЧ, если условиться, что генерируемые им числа не предсказуемы.

Вот только если условиться. На самом деле, если не использовать никаких апаратных средств (использование ввода пользователя), а только обходиться исключительно самой программой для генерации случайных чисел ->
это генерация псевдослучайных чисел.

Тем более если "пи" вычисляется с бесконечной точностью бесконечное время то необходимо сохранять результат вычислений,
а на это потребуется бесконечная память.

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

GC>Вот только если условиться. На самом деле, если не использовать никаких апаратных средств (использование ввода пользователя), а только обходиться исключительно самой программой для генерации случайных чисел ->
GC>это генерация псевдослучайных чисел.
Конечно условиться Эта условность накладывает ограничение на анализатор — он не должен знать устройство getNextNumberInPi.


GC>Тем более если "пи" вычисляется с бесконечной точностью бесконечное время то необходимо сохранять результат вычислений,
GC>а на это потребуется бесконечная память.
Зря я "пи" в пример привёл
Представьте себе, что есть некая волшебная функция getNextNumberInPi, которая возвращает очередное дробное число в числе "пи" (может, это число считает пользователь и по одной цифре с клавиатуры вводит ). Для того, чтобы узнать:

встречается последовательность цифр 8432741183478374439008753924

или нет, нам потребуется буфер для хранения всего лишь strlen ( "8432741183478374439008753924" ) == 28 символов. Первый же несовпавший символ очищает буфер и всё начинается сначала.

Здравствуйте, Alexey F, Вы писали:

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

GC>>Тем более если "пи" вычисляется с бесконечной точностью бесконечное время то необходимо сохранять результат вычислений,
GC>>а на это потребуется бесконечная память.
AF>Зря я "пи" в пример привёл
AF>Представьте себе, что есть некая волшебная функция getNextNumberInPi, которая возвращает очередное дробное число в числе "пи" (может, это число считает пользователь и по одной цифре с клавиатуры вводит ). Для того, чтобы узнать:
AF>

AF>встречается последовательность цифр 8432741183478374439008753924

AF>или нет, нам потребуется буфер для хранения всего лишь strlen ( "8432741183478374439008753924" ) == 28 символов. Первый же несовпавший символ очищает буфер и всё начинается сначала.

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

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

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

Python 2.5.1 (r251:54863, Apr 18 2007, 08:51:08) [MSC v.1310 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> 123 ** 123
11437436793461719009988029522806627674621807845185022977588797505236950478566689
64466065683652015421696499747277306288423453431965811348959199428208744498372120
99476648958359023796078549041949007807220625356526926729664064846685758382803707
100766740220839267L

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

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

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

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

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

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

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

Здравствуйте, 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. Но питон все равно имеет ограничение в размере ОЗУ,
например, не умеет обрабатывать числа, которые занимают памяти больше чем все ОЗУ компьютера (и жесткого диска).

Здравствуйте, 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;
        }
    }
}

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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>

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

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

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

Твой алгоритм явно нелинейный, так что будем ждать для любого нетривиального кода миллард-другой лет?

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

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

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

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

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

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

А говорят еще индусы злодеи. Хотя кто знает, может под ником GhostCoders какой-нибудь Брахмапутра тут решил над народом поиздеваться

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

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

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

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

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

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

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

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

PT>Мне почему-то сразу вот это напомнило:
PT>http://www.rus-os.narod.ru


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Насколько ваш алгоритм быстрее простого ожидания возврата из цикла?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сам пшел вон.

Учи компьютерную азбуку. А наверное бывший ветеринар программирует тут.

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

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

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

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

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

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

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

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

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

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

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

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

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

На практике (я имею в виду разумные ограничения по времени) можно использовать приемы "разделяй и властвуй" и подобные.

Здравствуйте, 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 шагов.

Так что любой общий алгоритм анализа — это изобретение вечного двигателя.

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

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

Боюсь, что пары миллиардов лет может нехватить. Насколько я помню, доказано, что невозможно построить машину тьюринга которая гарантированно определяет завершит любая другая машина тьюринга когда-либо работу или нет.

http://www.rsdn.ru/forum/message/3190404.1.aspx

Автор: CiViLiS
Дата: 27.11.08

Здравствуйте, 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>Так что любой общий алгоритм анализа — это изобретение вечного двигателя.
Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?

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

Простите, наверное, я начинаю уже Вас раздражать, но...
Итак, прежде, чем начать: я ни в коей мере не сомневаюсь в Ваших профессиональных способностях и не стремлюсь Вас задеть или оскорбить (я сам такой — каааак заболею идеей, так всё (последней болезнью у меня был архиватор, сжимающий любую последовательность в функцию ) ). О причинах, по которых я это всё пишу — см. ниже.

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

GC>Идет речь о "закрытых" участках кода, в которые информация из внешнего мира не поступает,
GC>а только обрабатываются.
Это и есть частные случаи, о который я говорил с самого начала.

Из Ваших ответов:

LF>Вы хотите сказать, что разрешили неразрешимую проблему?

Получается что так.

Получено решение не для общего случая, а для частного — когда система "замкнута". Неразрешимая проблема осталась таковой.

F>Что вы хотите услышать? Что разработчик, скачав утилиту и натравив ее на исходный код, получит (если получит) неоднозначные результаты и за это еще денег надо будет отвалить?

Вся фишка в том, что результаты будут 100% однозначные и 100% достоверные.

// Флейм пошёл из-за уверености в выделенном.
Полный перебор всех вариантов даст 100% однозначные и достоверные результаты, но "кому это надо" (c)? Если метод через 100 лет выдаст результат, что программа не зациклится, что с ним будут делать пра-правнуки того программиста, что запустил задачу на выполнение? А если алгоритм зацикливается и результаты его предсказать нельзя (скажем, алгоритм пользуется неким ГПСЧ, обладающий очень долго вычисляющимся алгоритмом (неупрощаемым) и проще запустить этот ГПСЧ и получить результат, чем пытаться предсказать (траты времени будут соответствующие))? Остановится через бесконечное время?

P.S.:

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

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

здесь же:

Устройство машины Тьюринга

В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

---

Лично я пытаюсь отговорить Вас от попытки распространить решение на все случаи и создавать некий инструмент, который будет 100% выдавать правильный результат. Число случаев использования такого инструмента будет сильно ограничено (мало разрабатываемых систем являются "закрытыми" без поступления внешних данных, а те элементарные функции, на которые можно будет анализатор натравить... Стоит ли овчинка выделки?).
Однако, раз Вы уж занялись этой проблемой, то у Вас может получится отличный полуавтоматический генератор юнит-тестов, который не будет выдавать информацию зациклилось/не зациклилось, а просто прогонит функцию по наибольшему количеству нужных данных :

int func ( int const arg ) {
    if ( arg < 2 ) {
       return -1;
    }
    else if ( arg * 2 > 15 ) {
        return 8;
    }
    else {
        return 5;
    }
}

А вот какой может получиться тест:

template<>
template<>
void object::test<1> () {
    set_test_name ( "int func ( int )" );
    ensure_equals ( func ( 0 ), -1 );
    ensure_equals ( func ( 10 ), 8 );
    ensure_equals ( func ( 4 ), 5 );
}

ИМХО, при рефакторинге такая штучка могла бы помочь... Вот только про её комерческую пользу — .

Здравствуйте, Alexander G, Вы писали:

AG>http://www.rsdn.ru/forum/message/3190404.1.aspx

Автор: CiViLiS
Дата: 27.11.08

Аааа, после того топика мне в голову пришла мысль о анализаторе, примерно о таком же, о котором пишет GhostCoders Перебор осмысленных вариантов на основе условий выполнения и условий циклов внутри тестируемой функции Только мысль была отметена за минуту

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

GC>Вот пример данной функции на этом языке:
GC>* This is function from RomikT *

Спасибо, что не поленился перевести!
А можно теперь условие n!=1 заменить на n>1 (RomikT там накосячил), и тип данных заменить на целые числа (или хотя бы 64-битные)?

Фишка исходной задачи тут:
http://en.wikipedia.org/wiki/Collatz_conjecture
http://mathworld.wolfram.com/CollatzProblem.html
если решишь для случая целых чисел (в математическом смысле), 1000 фунтов стерлингов получишь сразу, другие премии позже.

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

C>>Вот только это число растёт просто НЕВООБРАЗИМО быстро. Для машины Тьюринга с лентой из 6 элементов _нижняя_ граница составляет 10^1439 шагов (другой автор цитирует 4096 ^^ 166).
GC>Это зависит от числа возможных состояний головки машины Тьюринга. Чем оно больше тем больше шагов.
Для любого реального компьютера это число будет таким, что я даже не знаю как его записать.

C>>Причём не существует общих способов анализа проблемы останова для алгоритма, работающих за меньшее число шагов, чем сам алгоритм. Т.е. тебе для анализа вполне вероятно может потребоваться выполнить эти 10^1439 шагов.
GC>А за большее число шагов или за равное — существуют такие алгоритмы.
Тогда проще запустить сам алгоритм.

C>>Так что любой общий алгоритм анализа — это изобретение вечного двигателя.
GC>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?
Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx

Автор: Cyberax
Дата: 01.03.09

Здравствуйте, D. Mon, Вы писали:

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


DM>Фишка исходной задачи тут:
DM>http://en.wikipedia.org/wiki/Collatz_conjecture
DM>http://mathworld.wolfram.com/CollatzProblem.html
DM>если решишь для случая целых чисел (в математическом смысле), 1000 фунтов стерлингов получишь сразу, другие премии позже.

Доказывается элементарно.

Скажем если число N — четно, то оно уменьшается в два раза. То есть стремиться к единице. Тут все оцевидно.


Если число нечетно, то нечетно число O можно представить через четное число E следующим образом:

O = 2 * E + 1.

(Скажем 17 можно представить как 2 * 8 + 1), где O = 17, E = 8.

Для нечетных чисел производиться операция N = 3 * N + 1, то есть имеем следующее

O* = 3 * (2 * E + 1) + 1 = 6 * E + 3 + 1 = 6 * E + 4;

то есть на следующей итерации имеем число O* = 6 * E + 4;
Но оно всегда будет четным, так как если четно Е, то умножение четного числа на любое другое число
дает четное число, придавление 4 картины не изменеят, так как 4 — четное.

Следовательно, следующий шаг деление на 2.

Имеем O** = 3 * E + 2.
Число O** — тоже четное по тем же причинам.

Следовательно, следующий шаг деление на 2.
Имеем O*** = 3 * E / 2 + 1.

Несмотря на то что Е — четное, мы не может гарантировать что E / 2 — тоже четное.
Тут возможны обе ситуации.

Но имеет следующее.
Изначально мы имели нечетное число O, которое было равно O = 2 * E + 1.
после одного шага HOTPO, и двух шагов деления на 2, имеем O*** = 3 * E / 2 + 1.

Очевидно, что O*** < O.

(O*** всегда меньше O, для значений E > 1).

Получается что в любом случае, значение исходного числа N уменьшается, то есть стремиться к 1.
Через конечное число шагов мы получаем значение 1.

Где мои 1000 фунтов стерлингов???

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

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

C>>>Вот только это число растёт просто НЕВООБРАЗИМО быстро. Для машины Тьюринга с лентой из 6 элементов _нижняя_ граница составляет 10^1439 шагов (другой автор цитирует 4096 ^^ 166).
GC>>Это зависит от числа возможных состояний головки машины Тьюринга. Чем оно больше тем больше шагов.
C>Для любого реального компьютера это число будет таким, что я даже не знаю как его записать.

C>>>Причём не существует общих способов анализа проблемы останова для алгоритма, работающих за меньшее число шагов, чем сам алгоритм. Т.е. тебе для анализа вполне вероятно может потребоваться выполнить эти 10^1439 шагов.
GC>>А за большее число шагов или за равное — существуют такие алгоритмы.
C>Тогда проще запустить сам алгоритм.

C>>>Так что любой общий алгоритм анализа — это изобретение вечного двигателя.
GC>>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?
C>Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx

Автор: Cyberax
Дата: 01.03.09

Решение есть, только будет очень долгим. АНАЛИЗАТОР существует.

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

GC>Здравствуйте, D. Mon, Вы писали:

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


DM>>Фишка исходной задачи тут:
DM>>http://en.wikipedia.org/wiki/Collatz_conjecture
DM>>http://mathworld.wolfram.com/CollatzProblem.html
DM>>если решишь для случая целых чисел (в математическом смысле), 1000 фунтов стерлингов получишь сразу, другие премии позже.

GC>Доказывается элементарно.

GC>Скажем если число N — четно, то оно уменьшается в два раза. То есть стремиться к единице. Тут все оцевидно.


GC>Если число нечетно, то нечетно число O можно представить через четное число E следующим образом:

GC> O = 2 * E + 1.

Возьмём число 7 = 2 * 3 + 1

GC>(Скажем 17 можно представить как 2 * 8 + 1), где O = 17, E = 8.

GC>Для нечетных чисел производиться операция N = 3 * N + 1, то есть имеем следующее

GC> O* = 3 * (2 * E + 1) + 1 = 6 * E + 3 + 1 = 6 * E + 4;

GC>то есть на следующей итерации имеем число O* = 6 * E + 4;
GC>Но оно всегда будет четным, так как если четно Е, то умножение четного числа на любое другое число
GC>дает четное число, придавление 4 картины не изменеят, так как 4 — четное.

GC>Следовательно, следующий шаг деление на 2.

GC>Имеем O** = 3 * E + 2.

O** = 3 * 3 + 2 = 11

GC>Число O** — тоже четное по тем же причинам.

11 — чётное?
(ну и хотелось бы услышать, что за "те же причины")

Здравствуйте, Alexey F, Вы писали:

AF>Аааа, после того топика мне в голову пришла мысль о анализаторе, примерно о таком же, о котором пишет GhostCoders Перебор осмысленных вариантов на основе условий выполнения и условий циклов внутри тестируемой функции Только мысль была отметена за минуту

Рекомендую посмотреть, как работает Pex (сделанный в Microsoft Research). Была презентация на PDC.

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

GC>>>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?
C>>Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx

Автор: Cyberax
Дата: 01.03.09

GC>Решение есть, только будет очень долгим. АНАЛИЗАТОР существует.
Ну так какое решение-то? Перебрать все варианты циклов? Тогда это совершенно несерьёзно.

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

См. сюда: http://en.wikipedia.org/wiki/Satisfiability_Modulo_Theories и http://verify.stanford.edu/SVC/

Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны.

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

GC>Скажем если число N — четно, то оно уменьшается в два раза. То есть стремиться к единице. Тут все оцевидно.

Ошибка здесь. Это верно для степеней двойки, но не для всех четных чисел.

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

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

GC>>>>Тут я с вами не соглачен. Обший алгоритм анализа существует. Почему? Ответите аргументорованно?
C>>>Приведите пример решения двух простых задач: http://rsdn.ru/forum/message/3308701.1.aspx

Автор: Cyberax
Дата: 01.03.09

GC>>Решение есть, только будет очень долгим. АНАЛИЗАТОР существует.
C>Ну так какое решение-то? Перебрать все варианты циклов? Тогда это совершенно несерьёзно.

C>Нормальные статические валидаторы кода работают за счёт того, что строят логическую модель программы и пытаются в ней доказывать теоремы (о том, что имеем выход индекса за границу, обращение по невалидному указателю и т.п.). Если такая теорема доказывается — это означает ошибку.

C>См. сюда: http://en.wikipedia.org/wiki/Satisfiability_Modulo_Theories и http://verify.stanford.edu/SVC/

C>Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны.

Ещё по идее есть "обратный" подход — Total functional programming, в нём целеноправленно сделаны ограничения, чтобы получать явно завершающуюся программу. Правда, пока это до реальных реализации не дошло вроде как.

Здравствуйте, Курилка, Вы писали:

C>>Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны.
К>Ещё по идее есть "обратный" подход — Total functional programming, в нём целеноправленно сделаны ограничения, чтобы получать явно завершающуюся программу. Правда, пока это до реальных реализации не дошло вроде как.
Уже дошло, даже на практике начинает использоваться — http://augeas.net/

Нужно найти 123124.
На вход поступает 123123124.
Если мы очистим буфер (начнём поиск совпадения сначала) при поступлении второй 3, то пропустим совпадение.
Тут нужен сдвиг.
Это нечто вроде (а может и он самый) алгоритма Боуера-Мура поиска подстроки.

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

C>Здравствуйте, Курилка, Вы писали:

C>>>Эти методы реально работают и полезны, но они решают только весьма узкий диапазон задач, и без специальных эвристик и спец. обработки частных случаев на практике бесполезны.
К>>Ещё по идее есть "обратный" подход — Total functional programming, в нём целеноправленно сделаны ограничения, чтобы получать явно завершающуюся программу. Правда, пока это до реальных реализации не дошло вроде как.
C>Уже дошло, даже на практике начинает использоваться — http://augeas.net/

Чтот не вижу при чём тут TFP
Бумеранговские линзы гарантированно тотальны?
Ну и речь всёж идёт от языке общего применения.

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

SC>Нужно найти 123124.
SC>На вход поступает 123123124.
SC>Если мы очистим буфер (начнём поиск совпадения сначала) при поступлении второй 3, то пропустим совпадение.
SC>Тут нужен сдвиг.
SC>Это нечто вроде (а может и он самый) алгоритма Боуера-Мура поиска подстроки.

Да, я поторопился
Спасибо за уточнение

Здравствуйте, Курилка, Вы писали:

C>>Уже дошло, даже на практике начинает использоваться — http://augeas.net/
К>Чтот не вижу при чём тут TFP
К>Бумеранговские линзы гарантированно тотальны?
Нет, но они используют результаты исследований в области TFP.

К>Ну и речь всёж идёт от языке общего применения.
Это вряд ли.

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

GC>Реализовал транслятор простейшего языка программирования.
GC>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>и если зависает то на каких наборах данных.

Проверьте вашей программой вашу же программу

Здравствуйте, Курилка, Вы писали:

К>Ну и речь всёж идёт от языке общего применения.

Он же будет не Тьюринг полный.

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

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

К>>Ну и речь всёж идёт от языке общего применения.

FR>Он же будет не Тьюринг полный.

В том и смысл, что мощность машины Тьюринга избыточна, по меньшей мере для большинства задач.
Как пример — реальные машины не обладают бесконечной памятью (в отличие от классической МТ с бесконечной лентой)

Здравствуйте, Курилка, Вы писали:

К>В том и смысл, что мощность машины Тьюринга избыточна, по меньшей мере для большинства задач.

Есть куча задач где она недостаточна, ждем квантовые вычислители.
Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются

К>Как пример — реальные машины не обладают бесконечной памятью (в отличие от классической МТ с бесконечной лентой)

Ну для большинства задач вполне обладают.

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

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

К>>В том и смысл, что мощность машины Тьюринга избыточна, по меньшей мере для большинства задач.

FR>Есть куча задач где она недостаточна, ждем квантовые вычислители.
Т.е. есть более мощная вычислительная модель чем МТ?
Расскажи.
FR>Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются
Смысла предложения не понял

К>>Как пример — реальные машины не обладают бесконечной памятью (в отличие от классической МТ с бесконечной лентой)

FR>Ну для большинства задач вполне обладают.

Раскрой

Здравствуйте, Курилка, Вы писали:

FR>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>Т.е. есть более мощная вычислительная модель чем МТ?
К>Расскажи.

Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

FR>>Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются
К>Смысла предложения не понял

тут http://elementy.ru/lib/430319

Иными словами, при любом конечном наборе аксиом мы имеем бесконечное число истин, которые не могут быть доказаны с помощью этого набора.

Из неприводимости числа Ω следует, что всеобъемлющей математической теории существовать не может. Бесконечное множество битов Ω составляет бесконечное множество математических фактов (является ли каждый выбранный бит единицей или нулем), которые не могут быть выведены из каких бы то ни было принципов, более простых, чем сама последовательность битов. Значит, сложность математики бесконечна, тогда как любая отдельная теория «всего на свете» характеризуется конечной сложностью и, следовательно, не может охватить все богатство мира математических истин.

К>Раскрой

2^32 это очень не мало

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

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

FR>>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>>Т.е. есть более мощная вычислительная модель чем МТ?
К>>Расскажи.

FR>Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
FR>невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

Ммм, как-то не очень внятно, но допустим.

FR>>>Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются
К>>Смысла предложения не понял

FR>тут http://elementy.ru/lib/430319

FR>

FR>Иными словами, при любом конечном наборе аксиом мы имеем бесконечное число истин, которые не могут быть доказаны с помощью этого набора.

А также бесконечное число истин, которые могу быть доказаны

FR>

FR>Из неприводимости числа Ω следует, что всеобъемлющей математической теории существовать не может. Бесконечное множество битов Ω составляет бесконечное множество математических фактов (является ли каждый выбранный бит единицей или нулем), которые не могут быть выведены из каких бы то ни было принципов, более простых, чем сама последовательность битов. Значит, сложность математики бесконечна, тогда как любая отдельная теория «всего на свете» характеризуется конечной сложностью и, следовательно, не может охватить все богатство мира математических истин.

И в каком месте математики становятся "физиками"?

К>>Раскрой

FR>2^32 это очень не мало

Много и бесконечно — это довольно разные вещи.
Для вычисления "больших" задач бесконечная лента не нужна.

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

FR>>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>>Т.е. есть более мощная вычислительная модель чем МТ?
К>>Расскажи.
FR>Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
FR>невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

Что-то я у Пенроуза видел только предположения, что может существовать вычислительный квантовый процесс, превосходящий МТ. Типа, что он сможет придумывать новые истинные аксиомы, как это делают люди. Но ничего конкретного.

Разрабатываемые (и мыслимые) сейчас квантовые компьютеры не превосходят МТ.

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

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

FR>>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>>Т.е. есть более мощная вычислительная модель чем МТ?
К>>Расскажи.

FR>Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
FR>невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

вики, конечно, стрёмный источник, но всёж:

Although quantum computers may be faster than classical computers, those described above can't solve any problems that classical computers can't solve, given enough time and memory (albeit possibly an amount that could never practically be brought to bear).

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

Здравствуйте, Курилка, Вы писали:

К>Ммм, как-то не очень внятно, но допустим.

Внятнее тут http://ru.wikipedia.org/wiki/Алгоритмическая_неразрешимость

Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому вычислимых функций не более чем счётно. В то время как множество функций вида несчётно, если N счётно. Значит есть не вычислимые функции, причём их мощность больше, чем мощность вычислимых функций.

К>А также бесконечное число истин, которые могу быть доказаны

Смотри цитату выше, это разные бесконечности
Те которые можно доказать счетны, а недоказуемые (на данном наборе аксиом) нечетны, разница как между конечным и бесконечным.

К>И в каком месте математики становятся "физиками"?

В таком что математика такая же эксперементальная наука как и все остальные, с нее сняли корону

FR>>2^32 это очень не мало

К>Много и бесконечно — это довольно разные вещи.

Угу

К>Для вычисления "больших" задач бесконечная лента не нужна.

От задач зависит

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

FR>Смотри цитату выше, это разные бесконечности
FR>Те которые можно доказать счетны, а недоказуемые (на данном наборе аксиом) нечетны, разница как между конечным и бесконечным.

Не совсем так. Оба этих множества счетны, так как являются подмножествами счетного множества well-formed формул. Только множество доказуемых истин recursively enumerable, а недоказуемых — нет.

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


N>Что-то я у Пенроуза видел только предположения, что может существовать вычислительный квантовый процесс, превосходящий МТ. Типа, что он сможет придумывать новые истинные аксиомы, как это делают люди. Но ничего конкретного.

Угу.

N>Разрабатываемые (и мыслимые) сейчас квантовые компьютеры не превосходят МТ.

А вот это не доказано, есть только тезис Тьюринга, который не больше чем гипотеза.

Здравствуйте, Курилка, Вы писали:

К>По-моему ты подмешиваешь к просто мощности вычислительной модели (т.е. вопрос принципиальной выразимости выч. задач) ещё её скорость. Конечно, с практической т.зр. вопрос очень важный, но речь вроде не о нём шла.
К>Плюс я не уверен, что принципы TFP не применимы к квантовым вычислениям (хотя зарекаться не буду, т.к. не очень в них разбираюсь)

Насколько я понимаю никто пока ни доказал что квантовые вычисления эквивалентны машине Тьюринга, обратное тоже не доказано.

А с практической точки зрения никакие квантовые вычислители не нужны, достаточно аппаратной реализации недетерминированной машины Тьюринга http://ru.wikipedia.org/wiki/Недетерминированная_машина_Тьюринга (котороая теоретически равномощна обычной машине)

Здравствуйте, Курилка, Вы писали:

GC>>Имеем O** = 3 * E + 2.

К>O** = 3 * 3 + 2 = 11

GC>>Число O** — тоже четное по тем же причинам.

К>11 — чётное?
К>(ну и хотелось бы услышать, что за "те же причины")

Да, здесь ошибка, признаю.

O = 2 * E + 1

где O — нечетное число,
четным здесь является 2 * E — по определению,
а вот само E может быть как четным, так и нет

O* я вычислил правильно, но вот O** — неправильно.

Не получилось доказать. Бывает.

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

N>Не совсем так. Оба этих множества счетны, так как являются подмножествами счетного множества well-formed формул. Только множество доказуемых истин recursively enumerable, а недоказуемых — нет.

А разве общее множество всех формул не несчетно?

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

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

GC>>Реализовал транслятор простейшего языка программирования.
GC>>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>>и если зависает то на каких наборах данных.

T>Проверьте вашей программой вашу же программу

Нельзя по одной причине. Скажем моя программа состоит из С байт выполнимого кода и D байт обрабатываемых данных.
Если ее натравить саму на себя мы должны весь код программы и ее все данные передавать как данные в саму себя, то есть

D* = C + D

D** = C + D**

то есть вывод такой сама себя она не может анализировать.

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

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

N>>Не совсем так. Оба этих множества счетны, так как являются подмножествами счетного множества well-formed формул. Только множество доказуемых истин recursively enumerable, а недоказуемых — нет.

FR>А разве общее множество всех формул не несчетно?

Ну по идее есть же Гёделева нумерация (базис доказательства теоремы Гёделя), так что вполне себе счётно.

GhostCoders wrote:

> Не получилось доказать. Бывает.
А зачем ты сам пытаешься доказать? У тебя же есть этот простейший язык. Или внутре его неонка?

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

.>GhostCoders wrote:

>> Не получилось доказать. Бывает.
.>А зачем ты сам пытаешься доказать? У тебя же есть этот простейший язык. Или внутре его неонка?

Я хочу вам показать одну вещь.
Есть БОЛЬШАЯ разница между абстрактным алгоритмом вообще и его реализаией на реальной вычислительной машине.

Абстрактные алгоритмы используют понятие числа, переменной и т.д.
Но никто эти числа не ограничивает никак. В вычислителных машинах мы используем ограниченные области памяти для
хранения чисел — байты, слова, 32 битные значения, сейчас уже на 64 бит перешли.
Вот в этом и главная разница. Абстрактный алгоритм может уйти в бесконечность,
наш же реальный переполнится в какой-либо переменной, после максимального значения, переменная установиться в значение 0.

С помощью простейшего языка я методом перебора могу тебе дать гарантию что он не зависнит, например, на 10000 входных значений.

Здравствуйте, Курилка, Вы писали:

FR>>А разве общее множество всех формул не несчетно?

К>Ну по идее есть же Гёделева нумерация (базис доказательства теоремы Гёделя), так что вполне себе счётно.

Склероз мне подсказывает теорему Кантора
И этот же склероз подсказывает что Геделева нумерация как раз и выделяет счетное подмножество вычислимых формул из общего несчетного множества формул вообще (под формулой имеется в виду отображение счетного множества на четное же множество)

Выкладываю реализацию транслятора простейшего языка на С++
вместе с анализатором.

Код написал за 3-4 часа, качество, признаюсь УЖАСНОЕ, не до того было.
Он позволяет понять суть моего метода.

Это консольное приложение на С++. Аргументы командной строки следующие:
SimpleLanguageCompiler.exe имя_файла_на_простейшем_языке команда_что_делать

где
имя_файла_на_простейшем_языке — файл должен существовать и содержать в себе валидный текст на языке SL
команда_что_делать ключевое слово из следующих:
COMPILEONLY — транслирует входной текст на язык С++ (на выходе имеем файл с расширением .cpp),
который реализует данный алгоритм на SL
Этот файл можно откомпилировать компилятором MSVC (и думаю GCC тоже),
получить исполняемый .exe файл, который попросит у вас ввести все
значения для исходных переменных, начнет вычисление, и если алгортм не зависает,
в конце вычислений выдаст на экран значения результатов
(OUTPUT-переменные объявленные в заголовке программы)
Замечание. Компилировать этот .cpp файл можно из командной строки,
предварительно набрав: "%VS80COMNTOOLS%\vsvars32.bat"
что даст доступным компилятор cl.exe из командной строки,
потом вводим cl имя_файла.cpp
он компилируется, запускаем программу имя_файла.exe
и наслаждаемся результатом.

В этом режиме никаких проверок и анализов не производиться.

COMPILEWITHVALIDATE — подобно COMPILEONLY, только вставляется код для защиты от зависаний.
Если обнаружено зависание, на экран выведется соответствующее сообщение, и программа
терминирует.

TEST — получается файл, который тестирует программу на всех наборах значений. Выдает все значения
при которых программа зависает на экран. В конце выдает небольшую "статистику".


Хочется сказать, что многие программисты, изучая в институте машину Тьюринга,
конечно слышили о проблеме неразрешимости, так же как и о "вечном двигателе" и попытках создать его.
Но есть одно НО, машина Тьюринга бесконечна, для конечных машин, проблема зависания все же
РАЗРЕШИМА, хотя бы в теории. Про это обычно забывают, и в английской вики про это пишут,
что это распространенное заблуждение, что неразрешимость проблемы машины Тьюринга переносят
на конечные компьютеры. http://en.wikipedia.org/wiki/Halting_problem — сомтрите "Common pitfalls".

The halting problem is, in theory if not in practice, decidable for linear bounded automata (LBAs), or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:

"...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine..."(italics in original, Minsky 1967, p. 24)

Смысл в следующем. Что цикл зависания не может превосходить число внутренних состояний такой машины.

Ну а вот исходный текст АНАЛИЗАТОРА:

/*
* Copyright (c) 2009 by
* IP PETROV PETR PETROVICH.
* All Rights Reserved
*
* This software comprises unpublished confidential information
* including intellectual property of IP PETROV PETR PETROVICH.
* and may not be used, copied or made available to anyone, except in
* accordance with the licence under which it is furnished.
*
*/

#include "stdafx.h"

#define INT8 0
#define UINT8 1

int typec = 0; // 0 -compile. 1- validate, 2 — test

struct subprogram
{
std::string name;
std::vector<std::string> inputNames;
std::set<std::string> sinputNames;
std::vector<int> inputTypes;
std::vector<std::string> outputNames;
std::set<std::string> soutputNames;
std::vector<int> outputTypes;
std::vector<std::string> varNames;
std::set<std::string> svarNames;
std::vector<int> varTypes;
};

std::vector<subprogram> subprograms;
std::vector<subprogram> programs;
std::set<std::string> subprogram_names;
std::set<std::string> program_names;
std::string curContext;

int counter = 0;

void _fillstate(FILE* f,FILE* o)
{
counter++;

subprogram * sp = 0;

for(size_t i=0;i<subprograms.size();i++)
{
if (subprograms[i].name == curContext)
{
sp = &(subprograms[i]);
break;
}
}
for(size_t i=0;i<programs.size();i++)
{
if (programs[i].name == curContext)
{
sp = &(programs[i]);
break;
}
}
fprintf(o,"\t_curstate.line = %d;\n",counter++);

fprintf(o,"\t_curstate.variables.clear();\n",counter++);
for(size_t i=0;i<sp->inputNames.size();i++)
{
fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->inputNames[i].c_str());
}
for(size_t i=0;i<sp->outputNames.size();i++)
{
fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->outputNames[i].c_str());
}
for(size_t i=0;i<sp->varNames.size();i++)
{
fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->varNames[i].c_str());
}
}

void __check(FILE* f,FILE* o)
{
if (0 != typec)
{
_fillstate(f,o);
fprintf(o,"\t__check(&_curstate);\n");
}
}

int _subprogram(FILE* f,FILE* o,bool is_subprogram = true)
{
subprogram newSubprogram;
char name[5000] = { 0 };
fscanf(f,"%s",name);
if (subprogram_names.find(std::string(name)) != subprogram_names.end())
{
printf("error: subprogram %s is always defined\n",name);
return 0;
}
if (program_names.find(std::string(name)) != program_names.end())
{
printf("error: subprogram %s is always defined\n",name);
return 0;
}
curContext = std::string(name);
newSubprogram.name = std::string(name);
char next[5000] = { 0 };
fscanf(f,"%s",next);
while(strcmp(next,"BEGIN"))
{
if (!strcmp(next,"INPUT"))
{
char iname[5000] = { 0 };
fscanf(f,"%s",iname);
if (newSubprogram.sinputNames.find(std::string(iname)) != newSubprogram.sinputNames.end())
{
printf("error: input argument's name %s is always used\n",iname);
return 0;
}
if (newSubprogram.soutputNames.find(std::string(iname)) != newSubprogram.soutputNames.end())
{
printf("error: input argument's name %s is always used\n",iname);
return 0;
}
if (newSubprogram.svarNames.find(std::string(iname)) != newSubprogram.svarNames.end())
{
printf("error: input argument's name %s is always used\n",iname);
return 0;
}
newSubprogram.sinputNames.insert(std::string(iname));
newSubprogram.inputNames.push_back(std::string(iname));
char typeKeyword[5000] = { 0 };
fscanf(f,"%s",typeKeyword);
if (strcmp(typeKeyword,"TYPE"))
{
printf("error: TYPE keyword is absent\n");
return 0;
}
char _typename[5000] = { 0 };
fscanf(f,"%s",_typename);
if (!strcmp(_typename,"int8"))
{
newSubprogram.inputTypes.push_back(INT8);
}else
if (!strcmp(_typename,"uint8"))
{
newSubprogram.inputTypes.push_back(UINT8);
}else
{
printf("error: unknown type %s\n",_typename);
return 0;
}
}else
if (!strcmp(next,"OUTPUT"))
{
char oname[5000] = { 0 };
fscanf(f,"%s",oname);
if (newSubprogram.sinputNames.find(std::string(oname)) != newSubprogram.sinputNames.end())
{
printf("error: output argument's name %s is always used\n",oname);
return 0;
}
if (newSubprogram.soutputNames.find(std::string(oname)) != newSubprogram.soutputNames.end())
{
printf("error: output argument's name %s is always used\n",oname);
return 0;
}
if (newSubprogram.svarNames.find(std::string(oname)) != newSubprogram.svarNames.end())
{
printf("error: output argument's name %s is always used\n",oname);
return 0;
}
newSubprogram.soutputNames.insert(std::string(oname));
newSubprogram.outputNames.push_back(std::string(oname));
char typeKeyword[5000] = { 0 };
fscanf(f,"%s",typeKeyword);
if (strcmp(typeKeyword,"TYPE"))
{
printf("error: TYPE keyword is absent\n");
return 0;
}
char _typename[5000] = { 0 };
fscanf(f,"%s",_typename);
if (!strcmp(_typename,"int8"))
{
newSubprogram.outputTypes.push_back(INT8);
}else
if (!strcmp(_typename,"uint8"))
{
newSubprogram.outputTypes.push_back(UINT8);
}else
{
printf("error: unknown type %s\n",_typename);
return 0;
}
}else
if (!strcmp(next,"VAR"))
{
char vname[5000] = { 0 };
fscanf(f,"%s",vname);
if (newSubprogram.sinputNames.find(std::string(vname)) != newSubprogram.sinputNames.end())
{
printf("error: variable's name %s is always used\n",vname);
return 0;
}
if (newSubprogram.soutputNames.find(std::string(vname)) != newSubprogram.soutputNames.end())
{
printf("error: variable's name %s is always used\n",vname);
return 0;
}
if (newSubprogram.svarNames.find(std::string(vname)) != newSubprogram.svarNames.end())
{
printf("error: variable's name %s is always used\n",vname);
return 0;
}
newSubprogram.svarNames.insert(std::string(vname));
newSubprogram.varNames.push_back(std::string(vname));
char typeKeyword[5000] = { 0 };
fscanf(f,"%s",typeKeyword);
if (strcmp(typeKeyword,"TYPE"))
{
printf("error: TYPE keyword is absent\n");
return 0;
}
char _typename[5000] = { 0 };
fscanf(f,"%s",_typename);
if (!strcmp(_typename,"int8"))
{
newSubprogram.varTypes.push_back(INT8);
}else
if (!strcmp(_typename,"uint8"))
{
newSubprogram.varTypes.push_back(UINT8);
}else
{
printf("error: unknown type %s\n",_typename);
return 0;
}
}else
if (strcmp(next,"BEGIN"))
{
printf("error: waiting for BEGIN token\n");
return 0;
}
fscanf(f,"%s",next);
}

if (is_subprogram)
{
subprograms.push_back(newSubprogram);
subprogram_names.insert(std::string(name));
}else
{
programs.push_back(newSubprogram);
program_names.insert(std::string(name));
}

fprintf(o,"void %s (",name);
for(size_t i=0;i<newSubprogram.inputNames.size();i++)
{
if (newSubprogram.inputTypes[i] == INT8)
{
fprintf(o,"char ");
}else
if (newSubprogram.inputTypes[i] == UINT8)
{
fprintf(o,"unsigned char ");
}
fprintf(o,"&%s",newSubprogram.inputNames[i].c_str());
fprintf(o,", ");
}
for(size_t i=0;i<newSubprogram.outputNames.size();i++)
{
if (newSubprogram.outputTypes[i] == INT8)
{
fprintf(o,"char ");
}else
if (newSubprogram.outputTypes[i] == UINT8)
{
fprintf(o,"unsigned char ");
}
fprintf(o,"&%s",newSubprogram.outputNames[i].c_str());
fprintf(o,", ");
}

fprintf(o,"void* __dummy)\n");
fprintf(o,"{\n");

for(size_t i=0;i<newSubprogram.varNames.size();i++)
{
if (newSubprogram.varTypes[i] == INT8)
{
fprintf(o,"\tstatic char ");
}else
if (newSubprogram.varTypes[i] == UINT8)
{
fprintf(o,"\tstatic unsigned char ");
}
fprintf(o,"%s = 0;\n",newSubprogram.varNames[i].c_str());
}
for(size_t i=0;i<newSubprogram.outputNames.size();i++)
{
fprintf(o,"\t%s = 0;\n",newSubprogram.outputNames[i].c_str());
}
return 0;
}

void _inco(FILE* f,FILE *o)
{
__check(f,o);

char vname[5000] = { 0 };
fscanf(f,"%s",vname);

fprintf(o,"\t%s++;\n",vname);

}

void _deco(FILE* f,FILE *o)
{
__check(f,o);

char vname[5000] = { 0 };
fscanf(f,"%s",vname);

fprintf(o,"\t%s--;\n",vname);
}

void _mulo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s * %s;\n",vname1,vname2,vname3);
}

void _set(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
fprintf(o,"\t%s = %s;\n",vname1,vname2);
}

void _let(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
fprintf(o,"\t%s = %s;\n",vname1,vname2);
}


void _divo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s / %s;\n",vname1,vname2,vname3);
}

void _modo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s %% %s;\n",vname1,vname2,vname3);
}

void _addo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s + %s;\n",vname1,vname2,vname3);
}

void _subo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s — %s;\n",vname1,vname2,vname3);
}

void _label(FILE *f,FILE* o)
{
__check(f,o);

char name[5000] = { 0 };
fscanf(f,"%s",name);

fprintf(o,"label_%s_%s:\n",curContext.c_str(),name);
}

void _goto(FILE *f,FILE* o)
{
__check(f,o);

char name[5000] = { 0 };
fscanf(f,"%s",name);

fprintf(o,"\tgoto label_%s_%s;\n",curContext.c_str(),name);
}

void _ifequal(FILE *f,FILE* o)
{
__check(f,o);

char a1[5000] = { 0 };
fscanf(f,"%s",a1);
char a2[5000] = { 0 };
fscanf(f,"%s",a2);

fprintf(o,"\tif( %s == %s ) {\n\t",a1,a2);

char gotoK[5000] = { 0 };
fscanf(f,"%s",gotoK);
if (strcmp(gotoK,"GOTO"))
{
printf("error: waiting for GOTO keyword\n");
}

_goto(f,o);
fprintf(o,"\t}\n");

char e[5000] = { 0 };
fscanf(f,"%s",e);
if (!strcmp(e,"ELSE"))
{
fprintf(o,"\telse { \n\t");
_goto(f,o);
fprintf(o,"\t}\n");
}else
{
}
}

void _ifgreat(FILE *f,FILE* o)
{
__check(f,o);

char a1[5000] = { 0 };
fscanf(f,"%s",a1);
char a2[5000] = { 0 };
fscanf(f,"%s",a2);

fprintf(o,"\tif( %s > %s ) {\n\t",a1,a2);

char gotoK[5000] = { 0 };
fscanf(f,"%s",gotoK);
if (strcmp(gotoK,"GOTO"))
{
printf("error: waiting for GOTO keyword\n");
}

_goto(f,o);
fprintf(o,"\t}\n");

char e[5000] = { 0 };
fscanf(f,"%s",e);
if (!strcmp(e,"ELSE"))
{
fprintf(o,"\telse { \n\t");
_goto(f,o);
fprintf(o,"\t}\n");
}else
{
}
}

void _ifless(FILE *f,FILE* o)
{
__check(f,o);

char a1[5000] = { 0 };
fscanf(f,"%s",a1);
char a2[5000] = { 0 };
fscanf(f,"%s",a2);

fprintf(o,"\tif( %s < %s ) {\n\t",a1,a2);

char gotoK[5000] = { 0 };
fscanf(f,"%s",gotoK);
if (strcmp(gotoK,"GOTO"))
{
printf("error: waiting for GOTO keyword\n");
}

_goto(f,o);
fprintf(o,"\t}\n");

char e[5000] = { 0 };
fscanf(f,"%s",e);
if (!strcmp(e,"ELSE"))
{
fprintf(o,"\telse { \n\t");
_goto(f,o);
fprintf(o,"\t}\n");
}else
{
}
}

void _call(FILE *f,FILE* o)
{
__check(f,o);

char fname[5000] = { 0 };
fscanf(f,"%s",fname);

if (subprogram_names.find(std::string(fname)) != subprogram_names.end() )
{
for(size_t i=0;i<subprograms.size();i++)
{
if (subprograms[i].name == std::string(fname))
{
int ac = subprograms[i].inputNames.size() + subprograms[i].outputNames.size();
fprintf(o,"\t%s ( ",fname);
for(int k=0;k<ac;k++)
{
char an[5000] = { 0 };
fscanf(f,"%s",an);
fprintf(o,"%s,",an);
}
fprintf(o,"0);\n");

break;
}
}
}else
{
printf("error: subprogram is not founded %s\n",fname);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
printf("Simple Language Translator 1.0\n");
printf("Copyright (c) 2009 by\n");
printf("IP PETR PETROV PETROVICH.\n");
printf("All Rights Reserved.\n\n");

if (argc < 3)
{
printf("Usage: inputfilename.sl ACTION\n");
printf("\there ACTION can be the following:\n");
printf("\tCOMPILEONLY: A Simple Language Program will be compiled to C++ only\n");
printf("\tCOMPILEWITHVALIDATE: A Simple Language Program will be compiled to C++ with Halt-detection code\n");
printf("\tTEST: A simple Language Program will be tested (analised)\n");
return 0;
}

if (!strcmp(argv[2],"COMPILEONLY"))
{
typec = 0;
}else
if (!strcmp(argv[2],"COMPILEWITHVALIDATE"))
{
typec = 1;
}else
if (!strcmp(argv[2],"TEST"))
{
typec = 2;
}else
{
printf("error: incorrect mode\n");
return 0;
}


FILE *f = fopen(argv[1],"rt");
if (0 == f)
{
printf("Could not open input file.\n");
return 0;
}

std::string outfilename = std::string(argv[1]) + std::string(".cpp");
FILE *o = fopen(outfilename.c_str(),"wt");

if (0 == o)
{
printf("Could not create output file.\n");
return 0;
}

fprintf(o,"// This file was generated by Simple Language Translator 1.0\n");
fprintf(o,"// DO NOT EDIT THIS FILE\n\n");

fprintf(o,"#include <stdio.h>\n\n");

//!!!!
if (0 != typec)
{
fprintf(o,"#include <vector>\n\n");
fprintf(o,"struct _state{\n");
fprintf(o,"\tstd::vector<int> variables;\n");
fprintf(o,"\tint line;\n");
fprintf(o,"};\n\n");

fprintf(o,"std::vector<_state> _states;\n\n");

fprintf(o,"bool __compare(_state* s1,_state* s2)\n");
fprintf(o,"{\n");
fprintf(o,"\tif (s1->variables.size() != s2->variables.size()) return false;\n");
fprintf(o,"\tif (s1->line != s2->line) return false;\n");
fprintf(o,"\tfor(size_t i=0;i<s1->variables.size();i++)\n");
fprintf(o,"\t{\n");
fprintf(o,"\t\tif (s1->variables[i] != s2->variables[i]) return false;\n");
fprintf(o,"\t}\n");
fprintf(o,"\treturn true;\n");
fprintf(o,"}\n");

fprintf(o,"void __check(_state* s)\n");
fprintf(o,"{\n");
fprintf(o,"\tfor(size_t i=0;i<_states.size();i++)\n");
fprintf(o,"\t{\n");
fprintf(o,"\t\tif (__compare(s,&_states[i])) {\n");
if (1 == typec)
{
fprintf(o,"\t\t\tprintf(\"program has halted!\\n\");\n");
fprintf(o,"\t\t\texit(1);\n");
}else
if (2 == typec)
{
fprintf(o,"\t\t\tthrow int(1);\n");
}
fprintf(o,"\t\t}\n");
fprintf(o,"\t}\n");
fprintf(o,"\t_states.push_back(*s);\n");
fprintf(o,"}\n\n");
fprintf(o,"_state _curstate;\n");
}

bool comment = false;
bool wasprogram = false;
while(!feof(f))
{
char buff[5000] = { 0 };
fscanf(f,"%s",buff);

if (!strcmp(buff,"*"))
{
comment = !comment;
}else
{
if (!comment)
{
if (!strcmp(buff,"SUBPROGRAM"))
{
_subprogram(f,o,true);
}else
if (!strcmp(buff,"PROGRAM"))
{
if (!wasprogram)
{
_subprogram(f,o,false);
wasprogram = true;
}else
{
printf("error: a program must be one in file\n");
return 0;
}
}else
if (!strcmp(buff,"INC"))
{
_inco(f,o);
}else
if (!strcmp(buff,"DEC"))
{
_deco(f,o);
}else
if (!strcmp(buff,"MUL"))
{
_mulo(f,o);
}else
if (!strcmp(buff,"DIV"))
{
_divo(f,o);
}else
if (!strcmp(buff,"MOD"))
{
_modo(f,o);
}else
if (!strcmp(buff,"ADD"))
{
_addo(f,o);
}else
if (!strcmp(buff,"SUB"))
{
_subo(f,o);
}else
if (!strcmp(buff,"LABEL"))
{
_label(f,o);
}else
if (!strcmp(buff,"GOTO"))
{
_goto(f,o);
}else
if (!strcmp(buff,"IFEQUAL"))
{
_ifequal(f,o);
}else
if (!strcmp(buff,"IFGREAT"))
{
_ifgreat(f,o);
}else
if (!strcmp(buff,"IFLESS"))
{
_ifless(f,o);
}else
if (!strcmp(buff,"CALL"))
{
_call(f,o);
}else
if (!strcmp(buff,"SET"))
{
_set(f,o);
}else
if (!strcmp(buff,"LET"))
{
_let(f,o);
}else
if (!strcmp(buff,"END"))
{
fprintf(o,"\t;\n}\n");
}
}
}

//fprintf(o,"//%s\n",buff);
}

fprintf(o,"int main(int argc,char **argv)\n");
fprintf(o,"{\n");

if (0 == programs.size())
{
printf("error: no program\n");
return 0;
}

if (2 != typec)
{
fprintf(o,"\tint __temporary_var = 0;\n");
}

for(size_t i=0;i<programs[0].inputNames.size();i++)
{
if (programs[0].inputTypes[i] == INT8)
{
fprintf(o,"\tstatic char ");
}else
if (programs[0].inputTypes[i] == UINT8)
{
fprintf(o,"\tstatic unsigned char ");
}
if (2 == typec)
{
fprintf(o,"%s = 0, %s_copy = 0;\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
}else
{
fprintf(o,"%s = 0;\n",programs[0].inputNames[i].c_str());
}
if (2 != typec)
{
fprintf(o,"\tprintf(\"enter input variable %s:\\n\");\n",programs[0].inputNames[i].c_str());
fprintf(o,"\tscanf(\"%%d\",&__temporary_var);\n");

if (programs[0].inputTypes[i] == INT8)
{
fprintf(o,"\t%s = (char)__temporary_var;\n",programs[0].inputNames[i].c_str());
}else
if (programs[0].inputTypes[i] == UINT8)
{
fprintf(o,"\t%s = (unsigned char)__temporary_var;\n",programs[0].inputNames[i].c_str());
}
}

}

int c1 = 0;
if (2 == typec)
{
fprintf(o,"\tint __total = 0;\n");
fprintf(o,"\tint __total_halt = 0;\n");
for(size_t i=0;i<programs[0].inputNames.size();i++)
{
if (programs[0].inputTypes[i] == INT8)
{
c1++;
fprintf(o,"\tfor(int i%d=0;i%d<=255;i%d++)\n",c1,c1,c1);
fprintf(o,"\t{\n");
fprintf(o,"\t%s = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
fprintf(o,"\t%s_copy = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
}else
if (programs[0].inputTypes[i] == UINT8)
{
c1++;
fprintf(o,"\tfor(int i%d=-128;i%d<=127;i%d++)\n",c1,c1,c1);
fprintf(o,"\t{\n");
fprintf(o,"\t%s = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
fprintf(o,"\t%s_copy = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
}
}
}

for(size_t i=0;i<programs[0].outputNames.size();i++)
{
if (programs[0].outputTypes[i] == INT8)
{
fprintf(o,"\tstatic char ");
}else
if (programs[0].outputTypes[i] == UINT8)
{
fprintf(o,"\tstatic unsigned char ");
}
fprintf(o,"%s = 0;\n",programs[0].outputNames[i].c_str());
}

if (2 == typec)
{
fprintf(o,"\ttry { \n");
fprintf(o,"\t__total++;\n");
fprintf(o,"\t_states.clear();\n");
}

fprintf(o,"\t%s (",programs[0].name.c_str());
for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"%s,",programs[0].inputNames[i].c_str());
}
for(size_t i=0;i<programs[0].outputNames.size();i++)
{
fprintf(o,"%s,",programs[0].outputNames[i].c_str());
}
fprintf(o,"0);\n");

if (2 == typec)
{
fprintf(o,"\t} catch(int r){ \n");
fprintf(o,"\tif (1 == r) \n");
fprintf(o,"\t __total_halt++;\n");
fprintf(o,"\t printf(\"HALT HAS BEEN DETECTED.\\n\");\n");
fprintf(o,"\t printf(\"INPUT VARIABLES:\\n\");\n");

for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"\tprintf(\"%s = %%d\\n\",(int)%s_copy);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
}

fprintf(o,"\t}\n");

for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"\t}\n");
}
}

if (2 != typec)
{
fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
for(size_t i=0;i<programs[0].outputNames.size();i++)
{
fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].outputNames[i].c_str(),programs[0].outputNames[i].c_str());
}
}else
{
fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
fprintf(o,"\tprintf(\"total : %%d\\n\",__total);\n");
fprintf(o,"\tprintf(\"halted: %%d\\n\",__total_halt);\n");
fprintf(o,"\tprintf(\"passed: %%d\\n\",__total — __total_halt);\n");
fprintf(o,"\tprintf(\"Q = %%f\\n\",(double)__total_halt / (double)__total);\n");
}


/*fprintf(o,"\tprintf(\"RESULTS (inputs):\\n\");\n");
for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
}*/

fprintf(o,"}\n\n");

fclose(f);
fclose(o);

return 0;
}

С Уважением,
Петр Петров

Да, забыл форматирования для исходного кода сделать, вот:

/*
 * Copyright (c) 2009 by
 * IP PETROV PETR PETROVICH.
 * All Rights Reserved
 *
 * This software comprises unpublished confidential information
 * including intellectual property of IP PETROV PETR PETROVICH.
 * and may not be used, copied or made available to anyone, except in
 * accordance with the licence under which it is furnished.
 *
 */

#include "stdafx.h"

#define INT8  0
#define UINT8 1

int typec = 0; // 0 -compile. 1- validate, 2 - test

struct subprogram
{
    std::string name;
    std::vector<std::string> inputNames;
    std::set<std::string> sinputNames;
    std::vector<int> inputTypes;
    std::vector<std::string> outputNames;
    std::set<std::string> soutputNames;
    std::vector<int> outputTypes;
    std::vector<std::string> varNames;
    std::set<std::string> svarNames;
    std::vector<int> varTypes;
};

std::vector<subprogram> subprograms;
std::vector<subprogram> programs;
std::set<std::string> subprogram_names;
std::set<std::string> program_names;
std::string curContext;

int counter = 0;

void _fillstate(FILE* f,FILE* o)
{
    counter++;

    subprogram * sp = 0;

    for(size_t i=0;i<subprograms.size();i++)
    {
        if (subprograms[i].name == curContext)
        {
            sp = &(subprograms[i]);
            break;
        }
    }
    for(size_t i=0;i<programs.size();i++)
    {
        if (programs[i].name == curContext)
        {
            sp = &(programs[i]);
            break;
        }
    }
    fprintf(o,"\t_curstate.line = %d;\n",counter++);

      fprintf(o,"\t_curstate.variables.clear();\n",counter++);
      for(size_t i=0;i<sp->inputNames.size();i++)
      {
          fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->inputNames[i].c_str());
      }
      for(size_t i=0;i<sp->outputNames.size();i++)
      {
          fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->outputNames[i].c_str());
      }
      for(size_t i=0;i<sp->varNames.size();i++)
      {
          fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->varNames[i].c_str());
      }
}

void __check(FILE* f,FILE* o)
{
    if (0 != typec)
    {
        _fillstate(f,o);
        fprintf(o,"\t__check(&_curstate);\n");
    }
}

int _subprogram(FILE* f,FILE* o,bool is_subprogram = true)
{
  subprogram newSubprogram;
  char name[5000] = { 0 };
  fscanf(f,"%s",name);
  if (subprogram_names.find(std::string(name)) != subprogram_names.end())
  {
      printf("error: subprogram %s is always defined\n",name);
      return 0;
  }
  if (program_names.find(std::string(name)) != program_names.end())
  {
      printf("error: subprogram %s is always defined\n",name);
      return 0;
  }
  curContext = std::string(name);
  newSubprogram.name = std::string(name);
  char next[5000] = { 0 };
  fscanf(f,"%s",next);
  while(strcmp(next,"BEGIN"))
  {
      if (!strcmp(next,"INPUT"))
      {
            char iname[5000] = { 0 };
            fscanf(f,"%s",iname);
            if (newSubprogram.sinputNames.find(std::string(iname)) != newSubprogram.sinputNames.end())
            {
                printf("error: input argument's name %s is always used\n",iname);
                return 0;
            }
            if (newSubprogram.soutputNames.find(std::string(iname)) != newSubprogram.soutputNames.end())
            {
                printf("error: input argument's name %s is always used\n",iname);
                return 0;
            }
            if (newSubprogram.svarNames.find(std::string(iname)) != newSubprogram.svarNames.end())
            {
                printf("error: input argument's name %s is always used\n",iname);
                return 0;
            }
            newSubprogram.sinputNames.insert(std::string(iname));
            newSubprogram.inputNames.push_back(std::string(iname));
            char typeKeyword[5000] = { 0 };
            fscanf(f,"%s",typeKeyword);
            if (strcmp(typeKeyword,"TYPE"))
            {
                printf("error: TYPE keyword is absent\n");
                return 0;
            }
            char _typename[5000] = { 0 };
            fscanf(f,"%s",_typename);
            if (!strcmp(_typename,"int8"))
            {
                newSubprogram.inputTypes.push_back(INT8);
            }else
            if (!strcmp(_typename,"uint8"))
            {
                newSubprogram.inputTypes.push_back(UINT8);
            }else
            {
                printf("error: unknown type %s\n",_typename);
                return 0;                
            }
      }else
      if (!strcmp(next,"OUTPUT"))
      {
            char oname[5000] = { 0 };
            fscanf(f,"%s",oname);
            if (newSubprogram.sinputNames.find(std::string(oname)) != newSubprogram.sinputNames.end())
            {
                printf("error: output argument's name %s is always used\n",oname);
                return 0;
            }
            if (newSubprogram.soutputNames.find(std::string(oname)) != newSubprogram.soutputNames.end())
            {
                printf("error: output argument's name %s is always used\n",oname);
                return 0;
            }
            if (newSubprogram.svarNames.find(std::string(oname)) != newSubprogram.svarNames.end())
            {
                printf("error: output argument's name %s is always used\n",oname);
                return 0;
            }
            newSubprogram.soutputNames.insert(std::string(oname));
            newSubprogram.outputNames.push_back(std::string(oname));
            char typeKeyword[5000] = { 0 };
            fscanf(f,"%s",typeKeyword);
            if (strcmp(typeKeyword,"TYPE"))
            {
                printf("error: TYPE keyword is absent\n");
                return 0;
            }
            char _typename[5000] = { 0 };
            fscanf(f,"%s",_typename);
            if (!strcmp(_typename,"int8"))
            {
                newSubprogram.outputTypes.push_back(INT8);
            }else
            if (!strcmp(_typename,"uint8"))
            {
                newSubprogram.outputTypes.push_back(UINT8);
            }else
            {
                printf("error: unknown type %s\n",_typename);
                return 0;                
            }
      }else
      if (!strcmp(next,"VAR"))
      {
            char vname[5000] = { 0 };
            fscanf(f,"%s",vname);
            if (newSubprogram.sinputNames.find(std::string(vname)) != newSubprogram.sinputNames.end())
            {
                printf("error: variable's name %s is always used\n",vname);
                return 0;
            }
            if (newSubprogram.soutputNames.find(std::string(vname)) != newSubprogram.soutputNames.end())
            {
                printf("error: variable's name %s is always used\n",vname);
                return 0;
            }
            if (newSubprogram.svarNames.find(std::string(vname)) != newSubprogram.svarNames.end())
            {
                printf("error: variable's name %s is always used\n",vname);
                return 0;
            }
            newSubprogram.svarNames.insert(std::string(vname));
            newSubprogram.varNames.push_back(std::string(vname));
            char typeKeyword[5000] = { 0 };
            fscanf(f,"%s",typeKeyword);
            if (strcmp(typeKeyword,"TYPE"))
            {
                printf("error: TYPE keyword is absent\n");
                return 0;
            }
            char _typename[5000] = { 0 };
            fscanf(f,"%s",_typename);
            if (!strcmp(_typename,"int8"))
            {
                newSubprogram.varTypes.push_back(INT8);
            }else
            if (!strcmp(_typename,"uint8"))
            {
                newSubprogram.varTypes.push_back(UINT8);
            }else
            {
                printf("error: unknown type %s\n",_typename);
                return 0;                
            }
      }else
      if (strcmp(next,"BEGIN"))
      {
         printf("error: waiting for BEGIN token\n");
         return 0;                
      }
      fscanf(f,"%s",next);
  }

  if (is_subprogram)
  {
    subprograms.push_back(newSubprogram);
    subprogram_names.insert(std::string(name));
  }else
  {
    programs.push_back(newSubprogram);
    program_names.insert(std::string(name));
  }

  fprintf(o,"void %s (",name);
  for(size_t i=0;i<newSubprogram.inputNames.size();i++)
  {
      if (newSubprogram.inputTypes[i] == INT8)
      {
        fprintf(o,"char ");
      }else
      if (newSubprogram.inputTypes[i] == UINT8)
      {
        fprintf(o,"unsigned char ");
      }
      fprintf(o,"&%s",newSubprogram.inputNames[i].c_str());
      fprintf(o,", ");
  }
  for(size_t i=0;i<newSubprogram.outputNames.size();i++)
  {
      if (newSubprogram.outputTypes[i] == INT8)
      {
        fprintf(o,"char ");
      }else
      if (newSubprogram.outputTypes[i] == UINT8)
      {
        fprintf(o,"unsigned char ");
      }
      fprintf(o,"&%s",newSubprogram.outputNames[i].c_str());
      fprintf(o,", ");
  }

  fprintf(o,"void* __dummy)\n");
  fprintf(o,"{\n");

  for(size_t i=0;i<newSubprogram.varNames.size();i++)
  {
      if (newSubprogram.varTypes[i] == INT8)
      {
        fprintf(o,"\tstatic char ");
      }else
      if (newSubprogram.varTypes[i] == UINT8)
      {
        fprintf(o,"\tstatic unsigned char ");
      }
      fprintf(o,"%s = 0;\n",newSubprogram.varNames[i].c_str());
  }
  for(size_t i=0;i<newSubprogram.outputNames.size();i++)
  {
      fprintf(o,"\t%s = 0;\n",newSubprogram.outputNames[i].c_str());
  }
  return 0; 
}

void _inco(FILE* f,FILE *o)
{
    __check(f,o);

    char vname[5000] = { 0 };
    fscanf(f,"%s",vname);

    fprintf(o,"\t%s++;\n",vname);

}

void _deco(FILE* f,FILE *o)
{
    __check(f,o);

    char vname[5000] = { 0 };
    fscanf(f,"%s",vname);

    fprintf(o,"\t%s--;\n",vname);
}

void _mulo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s * %s;\n",vname1,vname2,vname3);
}

void _set(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    fprintf(o,"\t%s = %s;\n",vname1,vname2);
}

void _let(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    fprintf(o,"\t%s = %s;\n",vname1,vname2);
}


void _divo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s / %s;\n",vname1,vname2,vname3);
}

void _modo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s %% %s;\n",vname1,vname2,vname3);
}

void _addo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s + %s;\n",vname1,vname2,vname3);
}

void _subo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s - %s;\n",vname1,vname2,vname3);
}

void _label(FILE *f,FILE* o)
{
    __check(f,o);

    char name[5000] = { 0 };
    fscanf(f,"%s",name);

    fprintf(o,"label_%s_%s:\n",curContext.c_str(),name);
}

void _goto(FILE *f,FILE* o)
{
    __check(f,o);

    char name[5000] = { 0 };
    fscanf(f,"%s",name);

    fprintf(o,"\tgoto label_%s_%s;\n",curContext.c_str(),name);
}

void _ifequal(FILE *f,FILE* o)
{
    __check(f,o);

    char a1[5000] = { 0 };
    fscanf(f,"%s",a1);
    char a2[5000] = { 0 };
    fscanf(f,"%s",a2);

    fprintf(o,"\tif( %s == %s ) {\n\t",a1,a2);

    char gotoK[5000] = { 0 };
    fscanf(f,"%s",gotoK);
    if (strcmp(gotoK,"GOTO"))
    {
        printf("error: waiting for GOTO keyword\n");
    }

        _goto(f,o);
    fprintf(o,"\t}\n");

    char e[5000] = { 0 };
    fscanf(f,"%s",e);
    if (!strcmp(e,"ELSE"))
    {
        fprintf(o,"\telse { \n\t");
        _goto(f,o);
        fprintf(o,"\t}\n");
    }else
    {
    }
}

void _ifgreat(FILE *f,FILE* o)
{
    __check(f,o);

    char a1[5000] = { 0 };
    fscanf(f,"%s",a1);
    char a2[5000] = { 0 };
    fscanf(f,"%s",a2);

    fprintf(o,"\tif( %s > %s ) {\n\t",a1,a2);

    char gotoK[5000] = { 0 };
    fscanf(f,"%s",gotoK);
    if (strcmp(gotoK,"GOTO"))
    {
        printf("error: waiting for GOTO keyword\n");
    }

        _goto(f,o);
    fprintf(o,"\t}\n");

    char e[5000] = { 0 };
    fscanf(f,"%s",e);
    if (!strcmp(e,"ELSE"))
    {
        fprintf(o,"\telse { \n\t");
        _goto(f,o);
        fprintf(o,"\t}\n");
    }else
    {
    }
}

void _ifless(FILE *f,FILE* o)
{
    __check(f,o);

    char a1[5000] = { 0 };
    fscanf(f,"%s",a1);
    char a2[5000] = { 0 };
    fscanf(f,"%s",a2);

    fprintf(o,"\tif( %s < %s ) {\n\t",a1,a2);

    char gotoK[5000] = { 0 };
    fscanf(f,"%s",gotoK);
    if (strcmp(gotoK,"GOTO"))
    {
        printf("error: waiting for GOTO keyword\n");
    }

        _goto(f,o);
    fprintf(o,"\t}\n");

    char e[5000] = { 0 };
    fscanf(f,"%s",e);
    if (!strcmp(e,"ELSE"))
    {
        fprintf(o,"\telse { \n\t");
        _goto(f,o);
        fprintf(o,"\t}\n");
    }else
    {
    }
}

void _call(FILE *f,FILE* o)
{
    __check(f,o);

    char fname[5000] = { 0 };
    fscanf(f,"%s",fname);    

    if (subprogram_names.find(std::string(fname)) != subprogram_names.end() )
    {
        for(size_t i=0;i<subprograms.size();i++)
        {
            if (subprograms[i].name == std::string(fname))
            {
                int ac = subprograms[i].inputNames.size() + subprograms[i].outputNames.size();
                fprintf(o,"\t%s ( ",fname);
                for(int k=0;k<ac;k++)
                {
                    char an[5000] = { 0 };
                    fscanf(f,"%s",an);    
                    fprintf(o,"%s,",an);
                }
                fprintf(o,"0);\n");

                break;
            }
        }
    }else
    {
        printf("error: subprogram is not founded %s\n",fname);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
  printf("Simple Language Translator 1.0\n");
  printf("Copyright (c) 2009 by\n");
  printf("IP PETR PETROV PETROVICH.\n");
  printf("All Rights Reserved.\n\n");

  if (argc < 3)
  {
      printf("Usage: inputfilename.sl ACTION\n");
      printf("\there ACTION can be the following:\n");
      printf("\tCOMPILEONLY: A Simple Language Program will be compiled to C++ only\n");
      printf("\tCOMPILEWITHVALIDATE: A Simple Language Program will be compiled to C++ with Halt-detection code\n");
      printf("\tTEST: A simple Language Program will be tested (analised)\n");
      return 0;
  }

  if (!strcmp(argv[2],"COMPILEONLY"))
  {
      typec = 0;
  }else
  if (!strcmp(argv[2],"COMPILEWITHVALIDATE"))
  {
      typec = 1;
  }else
  if (!strcmp(argv[2],"TEST"))
  {
      typec = 2;
  }else
  {
      printf("error: incorrect mode\n");
      return 0;
  }


  FILE *f = fopen(argv[1],"rt");
  if (0 == f)
  {
      printf("Could not open input file.\n");
      return 0;
  }

  std::string outfilename = std::string(argv[1]) + std::string(".cpp");
  FILE *o = fopen(outfilename.c_str(),"wt");

  if (0 == o)
  {
      printf("Could not create output file.\n");
      return 0;
  }

  fprintf(o,"// This file was generated by Simple Language Translator 1.0\n");
  fprintf(o,"// DO NOT EDIT THIS FILE\n\n");

  fprintf(o,"#include <stdio.h>\n\n");  

  //!!!!
  if (0 != typec)
  {
  fprintf(o,"#include <vector>\n\n");  
  fprintf(o,"struct _state{\n");  
  fprintf(o,"\tstd::vector<int> variables;\n");  
  fprintf(o,"\tint line;\n");  
  fprintf(o,"};\n\n");  

  fprintf(o,"std::vector<_state> _states;\n\n");  

  fprintf(o,"bool __compare(_state* s1,_state* s2)\n");  
  fprintf(o,"{\n");  
  fprintf(o,"\tif (s1->variables.size() != s2->variables.size()) return false;\n");  
  fprintf(o,"\tif (s1->line != s2->line) return false;\n");  
  fprintf(o,"\tfor(size_t i=0;i<s1->variables.size();i++)\n");  
  fprintf(o,"\t{\n");  
  fprintf(o,"\t\tif (s1->variables[i] != s2->variables[i]) return false;\n");  
  fprintf(o,"\t}\n");  
  fprintf(o,"\treturn true;\n");  
  fprintf(o,"}\n");  

  fprintf(o,"void __check(_state* s)\n");  
  fprintf(o,"{\n");  
  fprintf(o,"\tfor(size_t i=0;i<_states.size();i++)\n");  
  fprintf(o,"\t{\n");  
  fprintf(o,"\t\tif (__compare(s,&_states[i])) {\n");  
  if (1 == typec)
  {
  fprintf(o,"\t\t\tprintf(\"program has halted!\\n\");\n");
  fprintf(o,"\t\t\texit(1);\n");
  }else
  if (2 == typec)
  {
  fprintf(o,"\t\t\tthrow int(1);\n");
  }
  fprintf(o,"\t\t}\n");  
  fprintf(o,"\t}\n");  
  fprintf(o,"\t_states.push_back(*s);\n");  
  fprintf(o,"}\n\n");  
  fprintf(o,"_state _curstate;\n");  
  }

  bool comment = false;
  bool wasprogram = false;
  while(!feof(f))
  {
      char buff[5000] = { 0 };
      fscanf(f,"%s",buff);

      if (!strcmp(buff,"*"))
      {
        comment = !comment;
      }else
      {
          if (!comment)
          {
              if (!strcmp(buff,"SUBPROGRAM"))
              {
                 _subprogram(f,o,true);
              }else
              if (!strcmp(buff,"PROGRAM"))
              {
                  if (!wasprogram)
                  {
                    _subprogram(f,o,false);
                    wasprogram = true;
                  }else
                  {
                      printf("error: a program must be one in file\n");
                      return 0;
                  }
              }else
              if (!strcmp(buff,"INC"))
              {
                  _inco(f,o);
              }else
              if (!strcmp(buff,"DEC"))
              {
                  _deco(f,o);
              }else
              if (!strcmp(buff,"MUL"))
              {
                  _mulo(f,o);
              }else
              if (!strcmp(buff,"DIV"))
              {
                  _divo(f,o);
              }else
              if (!strcmp(buff,"MOD"))
              {
                  _modo(f,o);
              }else
              if (!strcmp(buff,"ADD"))
              {
                  _addo(f,o);
              }else
              if (!strcmp(buff,"SUB"))
              {
                  _subo(f,o);
              }else
              if (!strcmp(buff,"LABEL"))
              {
                  _label(f,o);
              }else
              if (!strcmp(buff,"GOTO"))
              {
                  _goto(f,o);
              }else
              if (!strcmp(buff,"IFEQUAL"))
              {
                  _ifequal(f,o);
              }else
              if (!strcmp(buff,"IFGREAT"))
              {
                  _ifgreat(f,o);
              }else
              if (!strcmp(buff,"IFLESS"))
              {
                  _ifless(f,o);
              }else
              if (!strcmp(buff,"CALL"))
              {
                  _call(f,o);
              }else
              if (!strcmp(buff,"SET"))
              {
                  _set(f,o);
              }else
              if (!strcmp(buff,"LET"))
              {
                  _let(f,o);
              }else
              if (!strcmp(buff,"END"))
              {
                  fprintf(o,"\t;\n}\n");
              }
          }
      }
      
      //fprintf(o,"//%s\n",buff);
  }

  fprintf(o,"int main(int argc,char **argv)\n");
  fprintf(o,"{\n");

  if (0 == programs.size())
  { 
      printf("error: no program\n");
      return 0;
  }

  if (2 != typec)
  {
    fprintf(o,"\tint __temporary_var = 0;\n");
  }

  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      if (programs[0].inputTypes[i] == INT8)
      {
        fprintf(o,"\tstatic char ");
      }else
      if (programs[0].inputTypes[i] == UINT8)
      {
        fprintf(o,"\tstatic unsigned char ");
      }
      if (2 == typec)
      {
        fprintf(o,"%s = 0, %s_copy = 0;\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
      }else
      {
        fprintf(o,"%s = 0;\n",programs[0].inputNames[i].c_str());
      }
      if (2 != typec)
      {
          fprintf(o,"\tprintf(\"enter input variable %s:\\n\");\n",programs[0].inputNames[i].c_str());
          fprintf(o,"\tscanf(\"%%d\",&__temporary_var);\n");

          if (programs[0].inputTypes[i] == INT8)
          {
            fprintf(o,"\t%s = (char)__temporary_var;\n",programs[0].inputNames[i].c_str());
          }else
          if (programs[0].inputTypes[i] == UINT8)
          {
            fprintf(o,"\t%s = (unsigned char)__temporary_var;\n",programs[0].inputNames[i].c_str());
          }
      }
   
  }

  int c1 = 0;
  if (2 == typec)
  {
      fprintf(o,"\tint __total = 0;\n");
      fprintf(o,"\tint __total_halt = 0;\n");
      for(size_t i=0;i<programs[0].inputNames.size();i++)
      {
          if (programs[0].inputTypes[i] == INT8)
          {
              c1++;
             fprintf(o,"\tfor(int i%d=0;i%d<=255;i%d++)\n",c1,c1,c1);
             fprintf(o,"\t{\n");
             fprintf(o,"\t%s = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
             fprintf(o,"\t%s_copy = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
          }else
          if (programs[0].inputTypes[i] == UINT8)
          {
              c1++;
             fprintf(o,"\tfor(int i%d=-128;i%d<=127;i%d++)\n",c1,c1,c1);
             fprintf(o,"\t{\n");
             fprintf(o,"\t%s = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
             fprintf(o,"\t%s_copy = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
          }
      }
  }

  for(size_t i=0;i<programs[0].outputNames.size();i++)
  {
      if (programs[0].outputTypes[i] == INT8)
      {
        fprintf(o,"\tstatic char ");
      }else
      if (programs[0].outputTypes[i] == UINT8)
      {
        fprintf(o,"\tstatic unsigned char ");
      }
      fprintf(o,"%s = 0;\n",programs[0].outputNames[i].c_str());
  }

  if (2 == typec)
  {
      fprintf(o,"\ttry { \n");
      fprintf(o,"\t__total++;\n");
      fprintf(o,"\t_states.clear();\n");
  }

  fprintf(o,"\t%s (",programs[0].name.c_str());
  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      fprintf(o,"%s,",programs[0].inputNames[i].c_str());
  }
  for(size_t i=0;i<programs[0].outputNames.size();i++)
  {
      fprintf(o,"%s,",programs[0].outputNames[i].c_str());
  }
  fprintf(o,"0);\n");

  if (2 == typec)
  {
      fprintf(o,"\t} catch(int r){ \n");
      fprintf(o,"\tif (1 == r) \n");
      fprintf(o,"\t __total_halt++;\n");
      fprintf(o,"\t printf(\"HALT HAS BEEN DETECTED.\\n\");\n");
      fprintf(o,"\t printf(\"INPUT VARIABLES:\\n\");\n");

  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      fprintf(o,"\tprintf(\"%s = %%d\\n\",(int)%s_copy);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
  }

      fprintf(o,"\t}\n");

      for(size_t i=0;i<programs[0].inputNames.size();i++)
      {
          fprintf(o,"\t}\n");
      }
  }

  if (2 != typec)
  {
      fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
      for(size_t i=0;i<programs[0].outputNames.size();i++)
      {
          fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].outputNames[i].c_str(),programs[0].outputNames[i].c_str());
      }
  }else
  {
      fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
      fprintf(o,"\tprintf(\"total : %%d\\n\",__total);\n");
      fprintf(o,"\tprintf(\"halted: %%d\\n\",__total_halt);\n");
      fprintf(o,"\tprintf(\"passed: %%d\\n\",__total - __total_halt);\n");
      fprintf(o,"\tprintf(\"Q =  %%f\\n\",(double)__total_halt / (double)__total);\n");
  }


  /*fprintf(o,"\tprintf(\"RESULTS (inputs):\\n\");\n");
  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
  }*/

  fprintf(o,"}\n\n");

  fclose(f);
  fclose(o);

    return 0;
}

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

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

FR>>>А разве общее множество всех формул не несчетно?

К>>Ну по идее есть же Гёделева нумерация (базис доказательства теоремы Гёделя), так что вполне себе счётно.

FR>Склероз мне подсказывает теорему Кантора
А толку?
FR>И этот же склероз подсказывает что Геделева нумерация как раз и выделяет счетное подмножество вычислимых формул из общего несчетного множества формул вообще (под формулой имеется в виду отображение счетного множества на четное же множество)
Ничего она не выделяет, какие-то это твои домыслы. А счётное множество счётных множеств (наверное, ты это имел в виду под отображением) ровно также счётно. Тебя ведь не удивляет тот факт, что мощность множества рациональных чисел счётно?

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

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

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

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

FR>Угу, только есть пробема чтобы узнать эту псевдослучайную последовательность ее надо вычислять, а сходимость в заисимости от начальных условий, на современых машинах, у тех же аттракторов может быть от долей секунд до миллиардов лет.

Можете дать ссылку на такой Аттрактор? Очень интересно

GhostCoders wrote:

> Я хочу вам показать одну вещь.
> Есть БОЛЬШАЯ разница между абстрактным алгоритмом вообще и его
> реализаией на реальной вычислительной машине.
Кто бы мог подумать?!

> Абстрактные алгоритмы используют понятие числа, переменной и т.д.
> Но никто эти числа не ограничивает никак. В вычислителных машинах мы
> используем ограниченные области памяти для
> хранения чисел — байты, слова, 32 битные значения, сейчас уже на 64 бит
> перешли.
А вот в криптографии легко используют 4096-битные числа. Вот негодяи.
А ещё можно написать алгоритм, который будет использовать совсем немного памяти, но работать настолько долго, что это будет практически бесконечно.

> Вот в этом и главная разница. Абстрактный алгоритм может уйти в
> бесконечность,
Почитай о понятии "потенциальная бесконечность".

> наш же реальный переполнится в какой-либо переменной, после
> максимального значения, переменная установиться в значение 0.
Переполнится когда? И почему ты решил, что обязательно переполнится? А вдруг не переполнится, просто закончит работу через 10^1000 лет?

> С помощью простейшего языка я методом перебора могу тебе дать гарантию
> что он не зависнит, например, на 10000 входных значений.
Молодец. Только зачем это нужно?

Курилка wrote:

> Ну по идее есть же Гёделева нумерация
> <http://en.wikipedia.org/wiki/Goedel_numbering&gt; (базис доказательства
> теоремы Гёделя), так что вполне себе счётно.
Так это для некоего заданного формального языка (т.е. is a set of words, i.e. finite strings of letters, or symbols).

Но количество самих формальных языков — несчётно.

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

>> С помощью простейшего языка я методом перебора могу тебе дать гарантию
>> что он не зависнит, например, на 10000 входных значений.
.>Молодец. Только зачем это нужно?

В системах реального времени например. Даже могу дать гарантию что алгоритм будет выполняться не дольше чем
N шагов.

Когда есть информация для каждого входного набора за сколько шагов выполняется алгоритм такую информацию можно дать.
Всякие средние можно вычислять, минимумы, максимумы.

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

.>Курилка wrote:

>> Ну по идее есть же Гёделева нумерация
>> <http://en.wikipedia.org/wiki/Goedel_numbering&gt; (базис доказательства
>> теоремы Гёделя), так что вполне себе счётно.
.>Так это для некоего заданного формального языка (т.е. is a set of words, i.e. finite strings of letters, or symbols).

.>Но количество самих формальных языков — несчётно.

Докажи.
По-моему для языков можно также ввести нумерацию (формального доказательства не дам ) и получим счётное множество счётных множеств.

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

.>GhostCoders wrote:

>> Я хочу вам показать одну вещь.
>> Есть БОЛЬШАЯ разница между абстрактным алгоритмом вообще и его
>> реализаией на реальной вычислительной машине.
.>Кто бы мог подумать?!

>> Абстрактные алгоритмы используют понятие числа, переменной и т.д.
>> Но никто эти числа не ограничивает никак. В вычислителных машинах мы
>> используем ограниченные области памяти для
>> хранения чисел — байты, слова, 32 битные значения, сейчас уже на 64 бит
>> перешли.
.>А вот в криптографии легко используют 4096-битные числа. Вот негодяи.
.>А ещё можно написать алгоритм, который будет использовать совсем немного памяти, но работать настолько долго, что это будет практически бесконечно.

Да так оно и есть. Мой алгоритм будет анализировать его тоже много времени, практически бесконечно.

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

Курилка wrote:

> Докажи.
Диагонализацией доказывается.

> По-моему для языков можно также ввести нумерацию (формального
> доказательства не дам ) и получим счётное множество счётных множеств.
Счётное множество счётных множеств — счётно.

Какой бы мы язык не вводили, он всегда будет определять не более, чем конструктивное множество объектов.
Скажем, все действительные числа описать формальным языком нельзя.

GhostCoders wrote:

>> > С помощью простейшего языка я методом перебора могу тебе дать гарантию
>> > что он не зависнит, например, на 10000 входных значений.
> .>Молодец. Только зачем это нужно?
> В системах реального времени например. Даже могу дать гарантию что
> алгоритм будет выполняться не дольше чем
> N шагов.
Кому это нужно? Для таких тривиальных алгоритмов с 10000 значений проще заполнить таблицу в памяти, будет занимать всего 10кб.

> Когда есть информация для каждого входного набора за сколько шагов
> выполняется алгоритм такую информацию можно дать.
> Всякие средние можно вычислять, минимумы, максимумы
И с такой таблицей алгоритм сможет работать для каждого набора за один шаг.

> Да так оно и есть. Мой алгоритм будет анализировать его тоже много времени, практически бесконечно.
И накой он тогда?

> Но есть случаи когда мой алгоритм полезен. Это например, когда алгоритм
А я тоже алгоритм придумал — если в программе встречается число 42, то она зависнет.

> зацикливается со сравнительно небольшим временем работы. Такие зацикливания можно определять и делать для них юнит тесты
Вот у тебя есть алгоритм, который на вход берёт 2 числа длиной до 1000 десятичных цифр и выдаёт на выходе их произведение. Но из-за ошибки он зависает на числах 42*12345678901234567890. Оцени шанс, что твой алгоритм найдёт эту пару.

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

.>GhostCoders wrote:

>>> > С помощью простейшего языка я методом перебора могу тебе дать гарантию
>>> > что он не зависнит, например, на 10000 входных значений.
>> .>Молодец. Только зачем это нужно?
>> В системах реального времени например. Даже могу дать гарантию что
>> алгоритм будет выполняться не дольше чем
>> N шагов.
.>Кому это нужно? Для таких тривиальных алгоритмов с 10000 значений проще заполнить таблицу в памяти, будет занимать всего 10кб.

Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать

>> Когда есть информация для каждого входного набора за сколько шагов
>> выполняется алгоритм такую информацию можно дать.
>> Всякие средние можно вычислять, минимумы, максимумы
.>И с такой таблицей алгоритм сможет работать для каждого набора за один шаг.

>> Да так оно и есть. Мой алгоритм будет анализировать его тоже много времени, практически бесконечно.
.>И накой он тогда?

Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать

>> Но есть случаи когда мой алгоритм полезен. Это например, когда алгоритм
.>А я тоже алгоритм придумал — если в программе встречается число 42, то она зависнет.

>> зацикливается со сравнительно небольшим временем работы. Такие зацикливания можно определять и делать для них юнит тесты
.>Вот у тебя есть алгоритм, который на вход берёт 2 числа длиной до 1000 десятичных цифр и выдаёт на выходе их произведение. Но из-за ошибки он зависает на числах 42*12345678901234567890. Оцени шанс, что твой алгоритм найдёт эту пару.

Вероятность будет мизерной.

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

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

Об этом как раз и говорил Тьюринг — подобные анализаторы бесполезны, т.к. будут работать столько же по времени, сколько и алгоритм >_<

Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать

Какая разница, существует ли бесполезный анализатор или нет? Да и какой это "анализатор", честно говоря... Когда он не анализирует, а выполняет алгоритм. Что он ещё делает — см. ниже.

GC>Но есть случаи когда мой алгоритм полезен. Это например, когда алгоритм зацикливается со сравнительно
GC>небольшим временем работы. Такие зацикливания можно определять и делать для них юнит тесты
Прекрасно. Но зачем было писать, что у Вас есть:

AF>Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы зависания для любых возможных входных данных не может существовать. Мы можем сказать, что проблема зависания неразрешима на машине Тьюринга.

Это я уже давно знаю. Я смогу доказать что такие методы есть и работают.

Вся фишка в том, что результаты будут 100% однозначные и 100% достоверные.

т.е. что есть метод, который на все 100% для любого алгоритма всё раскажет и покажет?

Думаю, что из релиза Вы бы выкинули полный перебор всех вариантов, а таки сделали бы анализатор, который по условиям if и циклов подбирал бы только граничные значения (скажем, на условие if ( a < 0 ) { ... } можно взять два граничных значения: a < 0 (a == -1) и a > 0 (a == 1)). Да, это хорошая идея — если состояния начали повторяться, значит, код зависнет. Да, количество состояний конечно! Нельзя перехитрить такой анализатор, только сделать так, чтобы он "анализировал" до конца света... Или исчерпал всю свободную память.
Но Вы же сами говорили, что в отличие от машины Тьюринга, память у компьютеров ограничена. В какой такой памяти Вы будете хранить состояния вычислений?

int64_t func ( int64_t const a, int const b ) {
    for ( int64_t i = 0; i < b; ++i ) {
        if ( a + i + b == SOMETHING_CONST ) {
            return i;
        }
    }
    return 0;
}

Здесь всего лишь одна переменная, всё остальное — константы. Но всё равно, Вы задумались, где будете хранить максимум 2^64 8-байтных состояний этой простейшей функции?
А так:

double func2 ( double const a ) {
    for ( double i = 0; i < a; i += 0.000001 ) {
        double b = 42 * sqrt ( a + i );
        double c = 16 - b + i;
        if ( ( b * 2. ) - ( c / 2. ) + pow ( 2., i ) == SOMETHING_CONST ) {
            return i;
        }
    }
    return 0;
}

Это сколько памяти надо? Изменяются i, изменяется b, c тоже изменяется! А количество вызовов? При достаточно большом "a" это сколько памяти под состояния уйдёт и сколько она будет сравниваться с предыдущими? А если эти два метода вызываются из третьей функции? Или хотя бы первый метод вызывается пару раз из третьей функции.

Говорите, что ограничения современных компьютеров позволяют использовать Ваш метод и совершенно не учитываете, что Вашему методу нужен компьютер с нереально огромным количеством памяти Причём стремящегося к бесконечности для подавляющего большинства случаев

Какая разница между Вашим анализатором и анализируемой программой? Когда они оба выполняют один и тот же код? Почему бы просто не запустить оригинал и не посмотреть, завис он или нет? Ну хранит "анализатор" состояния и что? Знаете, насколько тривиальными должны быть случаи, чтобы этот анализатор работал разумное время и не съел всю доступную память? А с такими тривиальными случаями может справиться и человек.

Вот если бы анализировался исходный код, проверялись граничные условия, что-нибудь_ещё,_что_неизвестно_и_поэтому_нет_решения_проблемы_останова и всё это без запуска целевой программы... Тогда бы я понял поднятую здесь шумиху, разговоры о математике, ссылки на статьи и т.п.

Здравствуйте, Alexey F, Вы писали:

Вдогонку: ещё один пример, который не возьмёшь методом, основанным на сохранении состояний.
Сортировка массивов.
Да, обычная сортировка, хоть пузырьком, хоть быстрая.
Если, скажем, размер массива 5 миллиардов элементов (64-битная система), а для индексы использованы 32-битные — то она может зависнуть... Но прежде зависнет/грохнется анализатор, который не смог переварить такой объём данных. Это при том, что сортировка довольна элементарна (тот же пузырёк) и в самой программе, в большинстве случаев, используется для коротких массивов...

GhostCoders wrote:

> Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать
Существует способ перебрать 10000 значений? Алгоритм brute force думаю придумали сотни лет назад.

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

GC>Можете дать ссылку на такой Аттрактор? Очень интересно

здесь

Здравствуйте, Курилка, Вы писали:

FR>>Склероз мне подсказывает теорему Кантора
К>А толку?
FR>>И этот же склероз подсказывает что Геделева нумерация как раз и выделяет счетное подмножество вычислимых формул из общего несчетного множества формул вообще (под формулой имеется в виду отображение счетного множества на четное же множество)
К>Ничего она не выделяет, какие-то это твои домыслы. А счётное множество счётных множеств (наверное, ты это имел в виду под отображением) ровно также счётно. Тебя ведь не удивляет тот факт, что мощность множества рациональных чисел счётно?

Множество всех подмножеств счетного множества несчетно, это и есть теорема Кантора, и именно на ней базируется доказательство теоремы Геделя. В общем дальше надо искать учебники и смотреть, склероз

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

.>Курилка wrote:

>> Докажи.
.>Диагонализацией доказывается.
Ну вот и докажи

>> По-моему для языков можно также ввести нумерацию (формального
>> доказательства не дам ) и получим счётное множество счётных множеств.
.>Счётное множество счётных множеств — счётно.

.>Какой бы мы язык не вводили, он всегда будет определять не более, чем конструктивное множество объектов.
.>Скажем, все действительные числа описать формальным языком нельзя.

Т.е. ты говоришь, что есть формулы, которые записываются не языком, а чем-то ещё?
Приведи пример.

Здравствуйте, Курилка, Вы писали:

К>Т.е. ты говоришь, что есть формулы, которые записываются не языком, а чем-то ещё?
К>Приведи пример.

Та же проблема останова. Ее нельзя выразить в виде алгоритма. Но существовать как абстрактной формуле ей никто ни запрещает.

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

GC> Смысл в следующем. Что цикл зависания не может превосходить число внутренних состояний такой машины.

То есть твой анализатор практически бесполезен

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

.>GhostCoders wrote:

>> Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать
.>Существует способ перебрать 10000 значений? Алгоритм brute force думаю придумали сотни лет назад.

однако каков будет по твоему критерий останова?

например наш алгоритм выполняется, выполняется.... как определить что он завис?

Здравствуйте, Alexey F, Вы писали:

AF>Какая разница, существует ли бесполезный анализатор или нет? Да и какой это "анализатор", честно говоря... Когда он не анализирует, а выполняет алгоритм. Что он ещё делает — см. ниже.

Тут стирается граница между анализом и выполнением.
У нас есть M состояний (к сожаления M бывает часто огромным).
Из каждого состояния S (которое есть элемент множества M) мы детерминированно переходим
в другое состояние S*.
Есть подмножество M, которое есть начальные состояния (отличаются лишь входными данными).
Есть подмножество M, которое есть конечные состояния (на последней строке алгоритма, отличаются лишь состоянием резудьтирующих и временных переменных).

Рисуем М точек и соединяем их направленными стрелками. Получаем граф выполнения программы.
Если в графе есть циклы, значить здесь есть потенциальные зависания.
Зависания есть если в такой цикл можно попасть из какого-либо начального состояния.

Так что выполнение программы в этом случае сродни анализу графа,
путешествие по траектории смены состояний.

Есть быстрый способ проверить переходим ли мы из состояния S в состояние S* (за один шаг).
Однако нет быстрого способа определить наличие циклов в таком графе.


AF>Вот если бы анализировался исходный код, проверялись граничные условия, что-нибудь_ещё,_что_неизвестно_и_поэтому_нет_решения_проблемы_останова и всё это без запуска целевой программы... Тогда бы я понял поднятую здесь шумиху, разговоры о математике, ссылки на статьи и т.п.

Можно скажем ожидать зависания на на всех строках программы, а только на тех где есть условные переходы.
Запоминать состояние не всех переменных, о только тех, которые влияют на состояние переменных, участвующих в условии.
Незнаю насколько это

Здравствуйте, Alexey F, Вы писали:

AF>Получается что так.
AF>[/q]
AF>Получено решение не для общего случая, а для частного — когда система "замкнута". Неразрешимая проблема осталась таковой.

Машина Тьюринга также замкнута, у нее нет функций ввода-вывода с пользоватлелем.
Задается начальное состояние и вуаля — вперед.


Бесконечная лента хранит в каждой ячейке символ. Так что полное состояние системы бесконечно.

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

AF>>

AF>>"Если где-либо в дробной части числа "пи" встречается последовательность цифр 84327411834783744390087539249 — завершить цикл"

AF>>Что на это скажет анализатор?

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

Есть способ быстрого вычисления произвольной двоичной цифры числа пи без вычисления предыдущих цифр (см. ссылку здесь). Предлагается его запрограммить и прогнать через анализатор. Десятичную последовательность "843274118..." искать тяжеловато. Предлагается определить, содержится ли в двоичном представлении числа пи представление (например, Windows-1251) фразочки "Алан Тьюринг что-то накосячил со своей теоремой".

GhostCoders wrote:

> однако каков будет по твоему критерий останова?
А у тебя какой?

> например наш алгоритм выполняется, выполняется.... как определить что он
> завис?
Ограничить максимальное количество шагов.

Курилка wrote:

>> > Докажи.
> .>Диагонализацией доказывается.
> Ну вот и докажи
Да то же доказательство, что для действительных чисел. Построить таблицу "всех" формальных языков и выбирать с каждым элементом неравный язык. В общем в таком док-ве есть некие тонкие моменты, проще свести к действительным числам и сослаться уже на доказанную теорему.

> Т.е. ты говоришь, что есть формулы, которые записываются не языком, а
> чем-то ещё?
> Приведи пример.
Нет, проблема в том, что ты не можешь создать 1 такой язык, который будет описывать все возможные формулы.

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

.>GhostCoders wrote:

>> однако каков будет по твоему критерий останова?
.>А у тебя какой?

Если мы перешли в предыдущее состояние, в котором раньше уже были — то значить зависли.

>> например наш алгоритм выполняется, выполняется.... как определить что он
>> завис?
.>Ограничить максимальное количество шагов.

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

Плюс если алгоритм долго выполняется это не значить что он завис. Если же он перешел в одно из предыдуших состояний,
100% что он завис.

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

GC>Тут стирается граница между анализом и выполнением.
А не должна.

GC>Можно скажем ожидать зависания на на всех строках программы, а только на тех где есть условные переходы.
GC>Запоминать состояние не всех переменных, о только тех, которые влияют на состояние переменных, участвующих в условии.
GC>Незнаю насколько это
Повторюсь: с массивами что делать? Не всех переменных — хорошо, только срезать из них множно будет немного.
Отсюда, например, не срезать ни i, ни j, ни k:

for ( int i = 0; i < x; ++i ) {
    for ( int j = 0; j < i; ++j ) {
        for ( int k = 0; k < j; ++k ) {
            // ...
        }
    }
}

Здравствуйте, Alexey F, Вы писали:

AF>Повторюсь: с массивами что делать? Не всех переменных — хорошо, только срезать из них множно будет немного.
AF>Отсюда, например, не срезать ни i, ни j, ни k:

Да не нужно массивов, достаточно рекурсивных функций фибоначи или аккермана, там переменных то пара штук, но комбинаторный взрыв на числе вызовов, никакой памяти это проанализировать не хватит.