ビリャチピスデツナフイ Войти !bnw Сегодня Клубы

Мой код
http://govnokod.ru/15967
Машина Тьюринга с ограниченой лентой и без условия останова/недопустимой операцией -- будет зациклена. Т.е. ее состояние обязательно повторится когда-нибудь. По сути - конечный автомат

#X6YSEB / @j123123 / 3607 дней назад

Без удобной таблицы в которой хранятся правила работы для каждого состояния и входного символа это отстой
#X6YSEB/9F5 / @engineer / 3607 дней назад
@engineer DSL делаешь, который из удобной таблицы генерирует тебе сишкокод
#X6YSEB/3OU / @j123123 --> #X6YSEB/9F5 / 3607 дней назад
#define #define #define. Лень разбираться, спали входная строка конечного автомата в контексте МТ чем будет?
#X6YSEB/NYT / @kuzy000 / 3607 дней назад
@kuzy000 По всей видимости это будет та фигня, которая на ленту записана
#X6YSEB/4UL / @j123123 --> #X6YSEB/NYT / 3607 дней назад
@j123123 Точно нет, строчка может быть бесконечная, автомату похер.
#X6YSEB/R85 / @kuzy000 --> #X6YSEB/4UL / 3607 дней назад
@kuzy000 Эмм, ну тут у нас Машина Тьюринга с КОНЕЧНОЙ памятью. Т.е. это не совсем МТ
#X6YSEB/WUI / @j123123 --> #X6YSEB/R85 / 3607 дней назад
@kuzy000 Кстати, от бесконечной строки автомат неизбежно зависнет, это ж очевидно. Тут вот какое дело. И машина Тьюринга с конечной лентой, и конечный автомат, принимающий конечный набор входных данных, суть одно и то же. МТ с конечной памятью имеет ограниченое число внутренних состояний, и этот граф состояний можно нарисовать, если памяти хватит. Конечный автомат тоже может принимать на вход нечто конечной длинны, выплевывая на выходе нечто конечной длинны, у него тоже есть некий граф состояний, определяемый входным потоком и неким набором правил же! По сути мы получаем такую штуку. Берем входную строку конечной длины, получаем выходную строку конечной длинны (граф состояний, будь то МТ или конечный автомат) Понятно?
#X6YSEB/QKG / @j123123 --> #X6YSEB/R85 / 3607 дней назад
@kuzy000 Зависнет если нет условия останова. Ну тут и в МТ тоже никакого условия останова нет
#X6YSEB/HCM / @j123123 --> #X6YSEB/R85 / 3607 дней назад
@j123123 Пока что я вижу что ты просто написал программку которая проходится по массиву, это не МТ
#X6YSEB/VLC / @engineer --> #X6YSEB/QKG / 3607 дней назад
@engineer Чем это отличается от МТ?
#X6YSEB/JLN / @j123123 --> #X6YSEB/VLC / 3607 дней назад
@j123123 Тем что МТ определяется таблицей переходов, а ни её ни кода её интерпретации у тебя нет. С таким же успехом можно назвать компилятор gcc "машиной тьюринга" потому что для него можно написать простую её реализацию.
#X6YSEB/GYZ / @engineer --> #X6YSEB/JLN / 3607 дней назад
@engineer А какую тебе таблицу переходов запилить? Ну сделай там switch case, будет тебе таблица переходов. Это лишь готовый каркас для экспериментов
#X6YSEB/3JD / @j123123 --> #X6YSEB/GYZ / 3607 дней назад
@j123123 >Это лишь готовый каркас для экспериментов Ну да, это не МТ, МТ она видимо только в твоей голове. >А какую тебе таблицу переходов запилить Например такую: http://pastebin.com/ff1dYqbi <-- вот приличный пример реализации МТ
#X6YSEB/79T / @engineer --> #X6YSEB/3JD / 3607 дней назад
@engineer Сорь, но это какая-то неструктурированная неудобноваримая фигня
#X6YSEB/05Q / @j123123 --> #X6YSEB/79T / 3607 дней назад
@j123123 Эх ты, поехавший
#X6YSEB/7YF / @engineer --> #X6YSEB/05Q / 3607 дней назад
@engineer Примитивный (и при этом нечитаемый) код на си у него хороший, а высокоуровневый, полноценный, читаемый код на лиспе у него "неудобоваримый". И в каком мире ты живёшь?
#X6YSEB/TD4 / @engineer --> #X6YSEB/7YF / 3607 дней назад
@engineer Эхх, надо бы с тобой поговорить голосом
#X6YSEB/F94 / @j123123 --> #X6YSEB/TD4 / 3607 дней назад
@j123123 Уходишь от обсуждения.
#X6YSEB/3CM / @engineer --> #X6YSEB/F94 / 3607 дней назад
Я понял (вроде), как по МТ с конечной лентой построить конечный автомат, при этом алфавит автомата будет из одного символа, сжирая его он делает один шаг МТ.
#X6YSEB/KN2 / @kuzy000 / 3607 дней назад
@engineer Плюсую - поехваший. Давай таблицу автомата по какой-нибудь простенькой МТ.
#X6YSEB/JK5 / @kuzy000 --> #X6YSEB/7YF / 3607 дней назад
@kuzy000 Блджад, разве не очевидно? Ну смотри. Есть у тебя кусок памяти, на ней конечное число битиков. Есть функция, набор правил, который к битикам применяется. Предполагаем, что функция эта, принимая на вход набор битиков, возвращает новый набор битиков Т.е. получаем функцию bitarray = foo(bitarray); Учитывая что количество битиков у нас конечно и не может вылезти за пределы, число состояний системы конечно т.е. в какой-то момент система повторит свое состояние. Сами состояния можно записать в виде направленного графа, который может выглядеть так, как показано на рисунке https://i.imgur.com/RX2nSvo.jpg Скомпилируй мою программу, посмотри как там происходят переходы состояний и как оно в итоге приходит к равновесию и скачет около чего-то. Так вот, мы по сути берем строку конечного размера (в нее входит набор правил, применяемый к битикам и само начальное состояние этих самых битиков же ) и на выходе получаем ГРАФ ПЕРЕХОДОВ ИЗ СОСТОЯНИЯ В СОСТОЯНИЕ. Это штука конечной длинны. А теперь конечный автомат. В него мы передаем тоже некие байтики, и там тоже есть некий набор правил, который делает с этими байтиками что-то такое осмысленное, и.. меняется, у нас получается полная аналогия. Например, есть Conway's Game of Life, знаешь? На ограниченном игровом поле это конечный автомат, и можно аналогично построить граф состояний игрового поля. Если в игре жизнь у нас конечное игровое поле, из состояния A однозначно следует состояние Б, из состояния Б однозначно следует состояние В, и так по цепочке система эволюционирует, пока не ЗАЦИКЛИТСЯ, а зациклится она неизбежно, игровое поле конечно. Ну и на Машине Тьюринга вполне можно создать конечный автомат(ту же игру жизнь), а сам процессор/микроконтроллер/этц с конечной памятью, регистрами и оперативкой, если в нем нет случайностей - это по своей сути есть ни что иное, как конечный автомат. Ясно? Между тем, доказано что игра "Жизнь" является полной по Тьюрингу, если происходит на бесконечном игровом поле
#X6YSEB/M7S / @j123123 --> #X6YSEB/JK5 / 3607 дней назад
@j123123 > Учитывая что количество битиков у нас конечно и не может вылезти за пределы, число состояний системы конечно т.е. в какой-то момент система повторит свое состояние > количество битиков у нас конечно и не может вылезти за пределы > не может вылезти за пределы > По всей видимости это будет та фигня, которая на ленту записана > И машина Тьюринга с конечной лентой, и конечный автомат, принимающий конечный набор входных данных, суть одно и то же > конечный автомат, принимающий конечный набор входных данных Обычный конечный автомат (они не Тьюринг полные) может принимать сколько угодно входных данных. Если ты хочешь Тьюринг полный конечный автомат, у него должно быть бесконечное количество состояний (у машины Тьюринга конечное), то есть: Машина Тьюринга ~ Конечный автомат с бесконечным числом состояний (лол). Машина Тьюринга с конечной лентой ~ Конечный автомат. > у него тоже есть некий граф состояний, определяемый входным потоком и неким набором правил же! Только набором правил.
#X6YSEB/OQU / @kuzy000 --> #X6YSEB/M7S / 3607 дней назад
@kuzy000 >Обычный конечный автомат (они не Тьюринг полные) может принимать сколько угодно входных данных. Фххх. Я рассматриваю Машину Тьюринга с лентой конечной длины. У нас ИРЛ не существует Машин Тьюринга с бесконечной лентой (пока что я таких не обнаружил). >Если ты хочешь Тьюринг полный конечный автомат, у него должно быть бесконечное количество состояний (у машины Тьюринга конечное), то есть: >у него должно быть бесконечное количество состояний >у машины Тьюринга конечное ЛОЛЧТО? Короче... Я рассмативаю МТ с конечной лентой, она-то как раз аналогична конечному автомату т.к. имеет ограниченное число состояний. >Машина Тьюринга с конечной лентой ~ Конечный автомат. Я и рассматриваю тут МТ с конечной(ограниченной) лентой, если ты не заметил. Так что всё верно >>у него тоже есть некий граф состояний, определяемый входным потоком и неким набором правил же! >Только набором правил. Т.е. ты хочешь сказать что нам пофиг, что именно мы передаем в конечный автомат? (очевидно, это не так). И очевидно что конечный автомат что-то выдает на выходе, и это что-то определяется тем, что мы подали на вход и набором правил, НУ ПРЯМО КАК В МАШИНЕ ТЬЮРИНГА С КОНЕЧНОЙ ЛЕНТОЙ И НАБОРОМ ПРАВИЛ, КОТОРЫЕ ПРЕОБРАЗУЮТ СОСТОЯНИЕ ЛЕНТЫ ВО ЧТО-ТО НОВОЕ.
#X6YSEB/7IM / @j123123 --> #X6YSEB/OQU / 3607 дней назад
@j123123 Прочитай уже определение КА, на входе у него строка, на выходе у него только состояние. У машины Тьюринга, на входе лента, на выходе лента. То есть состояние МТ не тоже самое что состояние КА. Состояние МТ + лента (конечная) - тоже самое. По определению МТ, у нее конечное число состояний.
#X6YSEB/DS7 / @kuzy000 --> #X6YSEB/7IM / 3607 дней назад
@kuzy000 На вход подаешь хрень конечной длины - на выход получаешь хрень конечной длины. И Машина Тьюринга с лентой конечной длины и Конечный Автомат полностью УДОВЛЕТВОРЯЮТ ЭТОМУ КРИТЕРИЮ? (ДА/НЕТ) Микроконтроллер без случайностей это не конечный автомат? В конце концов можно на конечном автомате сделать ТАБЛИЦУ ПОИСКА. Смотри как получается. Есть у нас входная лента конечной длины, ну там нолики и единчики, A = 01010100011010...0 Берем мы эту, и представляем как ОДНО БОЛЬШОЕ ЧИСЛО из этого самого количества битов. Потом делаем.. switch (A) { case 01010100011010....: echo "некая_хуита1"; case 01010101111010....: echo "некая_хуита2"; case 11110101111010....: echo "некая_хуита3"; } Это не Конечный Автомат и не Машина Тьюринга с лентой конечной длины?
#X6YSEB/7SP / @j123123 --> #X6YSEB/DS7 / 3607 дней назад
@j123123 > В конце концов можно на конечном автомате сделать ТАБЛИЦУ ПОИСКА. Смотри как получается. Есть у нас входная лента конечной длины, ну там нолики и единчики, A = 01010100011010...0 Нельзя, у КА строка конечной длинны, но без ограничения по размеру, то есть ТАБЛИЦА ПОИСКА будет бесконечная. Для любящий примеры: конечный автомат принимающий ЛЮБОЕ натуральное число (допустим в двоичной форме) и определяющий его последнюю цифру. КАКАЯ НАХУЙ ТАБЛИЧКА? ДЛЯ ВСЕХ ЦИФР БЛЯДЬ? ТЫ ЕБАНУТЫЙ?
#X6YSEB/9HD / @kuzy000 --> #X6YSEB/7SP / 3607 дней назад
@kuzy000 s/ВСЕХ ЦИФР/ВСЕХ ЧИСЕЛ
#X6YSEB/DVN / @kuzy000 --> #X6YSEB/9HD / 3607 дней назад
@kuzy000 Это как раз ты ебанутый, блеать. Если лента конечная, там и количество возможных способов зависнуть в зависимости от того, какое было начальное состояние ленты на входе - КОНЕЧНО БЛЕАТЬ
#X6YSEB/K4K / @j123123 --> #X6YSEB/9HD / 3607 дней назад
@j123123 Пойми уже, в МТ вся ее охуенность не в бесконечной ленте, а в том, что ее (ленту) можно изменять. МТ не могущая изменять ленту не Тьюринг полна.
#X6YSEB/QUQ / @kuzy000 --> #X6YSEB/7SP / 3607 дней назад
@j123123 Ты разницу между конечным автоматом и машиной Тьюринга понимаешь?
#X6YSEB/6DJ / @kuzy000 --> #X6YSEB/K4K / 3607 дней назад
@kuzy000 Без бесконечной ленты, МТ сводится к конечному автомату. Объясняю еще раз. Берем конечную ленту. Передаем ее в МТ. Пусть МТ с конечной лентой делает много-много шагов. Каждый шаг должен (или не должен) каким-то образом менять ту фигню, которая на ленте записана. Поскольку лента конечна, число возможных состояний на ленте тоже конечно т.е. рано или поздно состояние после выполнения шага МТ с конечной лентой будет таким, каким оно было когда-то на одном из предыдущих шагов. Что это значит? Это значит что для любого начального состояния конечной ленты, мы можем построить последовательность шагов (ИСТОРИЮ ИЗМЕНЕНИЙ) ленты, и эта история всегда будет где-нибудь зацикливатся т.е. состояние повторится. Эту историю изменений для всех возможных начальных состояний конечной ленты можно выразить как таблицу поиска на конечных автоматах. ЯСНО?
#X6YSEB/MQE / @j123123 --> #X6YSEB/QUQ / 3607 дней назад
@j123123 Еще раз: > Лень разбираться, спали входная строка конечного автомата в контексте МТ чем будет? Hint: входная строка конечного автомата не имеет ограничений по размеру.
#X6YSEB/X7U / @kuzy000 --> #X6YSEB/MQE / 3607 дней назад
@kuzy000 >Hint: входная строка конечного автомата не имеет ограничений по размеру. И что ты хочешь этим сказать? Входная строка состоит из некоторого алфавита т.е. конечного набора символов(букв). Мы можем состояние любой ленты конечного размера обозначить как некую одну букву алфавита, которую принимает на вход КА и в ответ на которую получаем ответ через таблицу поиска. Когда мы говорим про то, что входная строка конечного автомата не имеет ограничений по размеру, это равносильно утверждению что вот у нас Машина Тьюринга, принимающая на вход ленту конечной длинны, но мы зато можем сначала одну конечную ленту дать, потом нам надоело и мы можем дать другую конечную ленту.
#X6YSEB/7WG / @j123123 --> #X6YSEB/X7U / 3607 дней назад
@kuzy000 Т.е. количество возможных букв алфавита конечно так же само, как конечно число состояний для конечной ленты. То, что мы можем сколько угодно букв (строку любой длинны) зафигачить в КА - пофиг. А если у нас есть возможность построить сколько угодно большой конечный автомат (построить таблицу поиска для всего) - мы получаем МТ
#X6YSEB/DWG / @j123123 --> #X6YSEB/X7U / 3607 дней назад
@j123123 Теперь ясно. Вначале ты говорил про посимвольную запись ленты, или я не так понял.
#X6YSEB/TE7 / @kuzy000 --> #X6YSEB/DWG / 3607 дней назад
@j123123 >А если у нас есть возможность построить сколько угодно большой конечный автомат (построить таблицу поиска для всего) - мы получаем МТ Да, тут еще и алфавит должен быть сколько угодно большим
#X6YSEB/4KE / @j123123 --> #X6YSEB/DWG / 3607 дней назад
ipv6 ready BnW для ведрофона BnW на Реформале Викивач Котятки

Цоперайт © 2010-2016 @stiletto.