![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Неспровоцированная мудрость
Jul. 5th, 2021 02:40 pmПоправил глупую опечатку в коде (inputes вместо inputs)? Сделай полнотекстовый поиск, возможно, есть ещё в одном месте. (Да, нашлась).
Jul. 5th, 2021
О задаче остановке и энтропии
Jul. 5th, 2021 03:21 pmВо-первых, давайте переформулируем, что такое "остановка". У нас нет остановки (машина не может остановиться), у нас есть бесконечный цикл, в котором состояние не меняется. Грубо говоря, loop {}. Легко показать, что если состояние машины (включая ленту) не поменялось в результате выполнения инструкции, то оно не поменяется никогда.
Дальше, если у нас нет понятия "остановка", то мы начинаем оперировать циклами. Цикл размера 0 (ноль инструкций, помимо инструкции повтора) - это аналог "остановки", но произойти он может не только в результате достижения конца алгоритма, но и в любой другой момент времени. Мы теряем при этом возможность знать, что на ленте тот результат, который был задуман но, в целом, мы не можем этого знать и в контексте halt инструкции, потому что из-за ошибки в коде мы можем перейти на halt до выводе результата целиком. Другими словами, если мы договоримся, что loop{} - это аналог halt, то будет результат или нет в этот момент на выводе - это добрая воля программы.
Далее: у нас не может быть циклов состояний машины размером 1 (заметим, не инструкций, а состояний). Любая циклическая операция требует как минимум два состояния между которыми будут переходы, потому что переход из состояния в само себя - это цикл размера 0, а переход в другое состояние оставляет машину в новом состоянии, и для "зацикливания" ей нужно перейти в состояние до первого изменения, т.е. размеры циклов 0, 2. Циклы размером 3, впрочем, быть могут (loop{ a=1; a=2; a=3;}). Заметим, loop{a=1} имеет размер 0, т.к. состояние a=1 не меняется между циклами.
Некоторые состояния программы не могут быть повторены, и являются уникальными. Программа начинает свою работу из уникального состояния, и продолжает перемещаться, пока не достигнет бесконечного цикла. бесконечный цикл (состояния) может быть только один, потому что для перехода во второй, нам надо досчитать до бесконечности.
Некоторые программы имеют нулевой начальный путь, т.е. они начинают с состояния, которое достигают снова и снова.
Вне зависимости от размера цикла, как только программа достигла повторяемого состояния (цикла), она может считаться "завершённой" (в том смысле, что достигла бесконечно повторяющегося цикла). Даже если этот цикл - поиск ответа на вопрос 42, занимающий квинтилионы лет. Заметим, в этом месте у нас отсутствуют side effects и side causes, потому что при их наличии у нас может и не быть (в общем случае) повторяющегося цикла.
Таким образом, программа начинает с неповторяющейся последовательности состояний (возможно, нулевой длинны), и переходит в повторяющийся цикл состояний.
Если мы примем процесс перехода от инструкции к инструкции аналогом "времени", то мы можем представить себе "энтропию" машины, как описание вероятности состояния, в котором находится машина. С учётом, что цикл состояния выполняется бесконечно много, вне зависимости от того, сколько состояний в цикле, энтропия каждого состояния в цикле бесконечна (бесконечность, делёная на конечное число), а энтропия уникальных состояний - нулевая.
Конечная тьюринг-машина всегда стремится перейти из состояние низкой энтропии в состояние высокой энтропии, либо уже находится в состоянии бесконечной энтропии. Бесконечная машина Тьюринга может оттягивать этот процесс бесконечно долго.
Линейный код не может иметь в своём составе циклов, то есть в нём машина находится в состоянии нулевой энтропии. При том, что машина находится в состоянии нулевой энтропии, она всё равно двигается в сторону увеличения энтропии, потому что когда линейный код заканчивается, дальше там либо ещё линейный код (конечного размера), либо цикл (бесконечная энтропия).
Чтобы перестать считать нули и бесконечность, можно перенормировать понятие энтропии, как 1/(число шагов), оставшихся до начала цикла. В этом случае цикл - это бесконечность, начальное состояние - минимальная энтропия, равная максимальному времени выполнения неповтояющейся части программы. В момент, когда программа выполняет последнюю нециклическую инструкцию, энтропия равна 1.
Для конечного компьютера без учёта side effects/causes, максимальный размер неповторяющейся программы - это время пересчёта всех состояний машины (например, от максимального до нулевого с зацикливанием на нуле - если зацикливание произойдёт не на нуле, то размер цикла больше, уникальных состояний меньше). Пренебрегая регистрами, для идеализированного компьютера, это примерно 28*mem_in_bytes-1 состояний.
Задача остановки компьютера в такой терминологии сводится к поиску циклов. Поскольку цикл состояний один, достаточно найти любой цикл, и этого достаточно для определения остановки. При конечных компьютерах эта задача имеет теоретическое простое решение: через 28*mem_in_bytes состояний компьютер гарантировано находится в зацикленном состоянии, достаточно просто подождать/смоделировать это количество инструкций и быть уверенным, что программа зациклилась. Для бесконечного компьютера это не работает - простейшее loop {a+=1} не завершится никогда, но и цикла не создаст никогда. В этой ситуации машина находится в состоянии нулевой энтропии (по любому из определений), и переходит в состояние нулевой энтропии, ненулевых значений у такой машины нет.
Я не знаю, зачем я всё это писал, но мне понравилась идея про "энтропию" машины. Есть время или его подобие - есть энтропия.
Дальше, если у нас нет понятия "остановка", то мы начинаем оперировать циклами. Цикл размера 0 (ноль инструкций, помимо инструкции повтора) - это аналог "остановки", но произойти он может не только в результате достижения конца алгоритма, но и в любой другой момент времени. Мы теряем при этом возможность знать, что на ленте тот результат, который был задуман но, в целом, мы не можем этого знать и в контексте halt инструкции, потому что из-за ошибки в коде мы можем перейти на halt до выводе результата целиком. Другими словами, если мы договоримся, что loop{} - это аналог halt, то будет результат или нет в этот момент на выводе - это добрая воля программы.
Далее: у нас не может быть циклов состояний машины размером 1 (заметим, не инструкций, а состояний). Любая циклическая операция требует как минимум два состояния между которыми будут переходы, потому что переход из состояния в само себя - это цикл размера 0, а переход в другое состояние оставляет машину в новом состоянии, и для "зацикливания" ей нужно перейти в состояние до первого изменения, т.е. размеры циклов 0, 2. Циклы размером 3, впрочем, быть могут (loop{ a=1; a=2; a=3;}). Заметим, loop{a=1} имеет размер 0, т.к. состояние a=1 не меняется между циклами.
Некоторые состояния программы не могут быть повторены, и являются уникальными. Программа начинает свою работу из уникального состояния, и продолжает перемещаться, пока не достигнет бесконечного цикла. бесконечный цикл (состояния) может быть только один, потому что для перехода во второй, нам надо досчитать до бесконечности.
Некоторые программы имеют нулевой начальный путь, т.е. они начинают с состояния, которое достигают снова и снова.
Вне зависимости от размера цикла, как только программа достигла повторяемого состояния (цикла), она может считаться "завершённой" (в том смысле, что достигла бесконечно повторяющегося цикла). Даже если этот цикл - поиск ответа на вопрос 42, занимающий квинтилионы лет. Заметим, в этом месте у нас отсутствуют side effects и side causes, потому что при их наличии у нас может и не быть (в общем случае) повторяющегося цикла.
Таким образом, программа начинает с неповторяющейся последовательности состояний (возможно, нулевой длинны), и переходит в повторяющийся цикл состояний.
Если мы примем процесс перехода от инструкции к инструкции аналогом "времени", то мы можем представить себе "энтропию" машины, как описание вероятности состояния, в котором находится машина. С учётом, что цикл состояния выполняется бесконечно много, вне зависимости от того, сколько состояний в цикле, энтропия каждого состояния в цикле бесконечна (бесконечность, делёная на конечное число), а энтропия уникальных состояний - нулевая.
Конечная тьюринг-машина всегда стремится перейти из состояние низкой энтропии в состояние высокой энтропии, либо уже находится в состоянии бесконечной энтропии. Бесконечная машина Тьюринга может оттягивать этот процесс бесконечно долго.
Линейный код не может иметь в своём составе циклов, то есть в нём машина находится в состоянии нулевой энтропии. При том, что машина находится в состоянии нулевой энтропии, она всё равно двигается в сторону увеличения энтропии, потому что когда линейный код заканчивается, дальше там либо ещё линейный код (конечного размера), либо цикл (бесконечная энтропия).
Чтобы перестать считать нули и бесконечность, можно перенормировать понятие энтропии, как 1/(число шагов), оставшихся до начала цикла. В этом случае цикл - это бесконечность, начальное состояние - минимальная энтропия, равная максимальному времени выполнения неповтояющейся части программы. В момент, когда программа выполняет последнюю нециклическую инструкцию, энтропия равна 1.
Для конечного компьютера без учёта side effects/causes, максимальный размер неповторяющейся программы - это время пересчёта всех состояний машины (например, от максимального до нулевого с зацикливанием на нуле - если зацикливание произойдёт не на нуле, то размер цикла больше, уникальных состояний меньше). Пренебрегая регистрами, для идеализированного компьютера, это примерно 28*mem_in_bytes-1 состояний.
Задача остановки компьютера в такой терминологии сводится к поиску циклов. Поскольку цикл состояний один, достаточно найти любой цикл, и этого достаточно для определения остановки. При конечных компьютерах эта задача имеет теоретическое простое решение: через 28*mem_in_bytes состояний компьютер гарантировано находится в зацикленном состоянии, достаточно просто подождать/смоделировать это количество инструкций и быть уверенным, что программа зациклилась. Для бесконечного компьютера это не работает - простейшее loop {a+=1} не завершится никогда, но и цикла не создаст никогда. В этой ситуации машина находится в состоянии нулевой энтропии (по любому из определений), и переходит в состояние нулевой энтропии, ненулевых значений у такой машины нет.
Я не знаю, зачем я всё это писал, но мне понравилась идея про "энтропию" машины. Есть время или его подобие - есть энтропия.
CI без сервера
Jul. 5th, 2021 08:56 pmА вот у меня есть такой запрос: я хочу иметь CI-подобный инструмент (задачи/автоматически вычисляемые зависимости порядка выполнения, параметры, matrix и т.д.), но без сервера. Чтобы не было веб-морды и сервера, а было что-то вида
`ci-run ci.yaml` (в чём эта штука выполняется - следующий вопрос). И чтобы из ci.yaml автоматически вытекало всё остальное. Логи на экран, что выполнять, статусы, зависимости, cleanup и т.д.
Разумеется, opensource. Что-то мне в голову ничего не приходит.
`ci-run ci.yaml` (в чём эта штука выполняется - следующий вопрос). И чтобы из ci.yaml автоматически вытекало всё остальное. Логи на экран, что выполнять, статусы, зависимости, cleanup и т.д.
Разумеется, opensource. Что-то мне в голову ничего не приходит.