От kinetic
К Грозный
Дата 31.08.2006 00:53:45
Рубрики Политек; Космос;

Re: [2СанитарЖеня] кибернетику,

>>Что есть любое цифровое устройство? Конечный автомат или совокупность конечных автоматов.
>
>*Любое* цифровое устройство есть совокупность конечных автоматов.

>Утверждение неверное.

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

Штука в том, что у "цифрового устройсва" под названием компьютер пространство состояний, входной и выходной алфавиты огромны. Даже для пустячного устройства у которого ВСЯ память (регистры + ОЗУ + внешняя память) занимает один килобайт, число состояний = 2^1000 ~ 10^250, т.е. больше или сравнимо с числом частиц во Вселенной. По этой причине формальной теории удобнее рассматривать такой автомат как машину с бесконечным числом состояний, т.е. как машину Тьюринга.
От А.Погорилый
К kinetic (31.08.2006 00:53:45)
Дата 31.08.2006 18:59:53

Re: [2СанитарЖеня] кибернетику,

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

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

Да, конечно. И реализовать его как один конечный автомат - громоздко до нереализуемости.
Но я это привел исключительно к тому, что все, что делается на троичной, пятеричной и т.д. логике - делается и на двоичной. То есть никаких принципиально новых логических возможностей троичная логика в сравнении с двоичной не несет. Все реализуется и на двоичной.
От Грозный
К kinetic (31.08.2006 00:53:45)
Дата 31.08.2006 03:56:06

Re: [2СанитарЖеня] кибернетику,

>>>Что есть любое цифровое устройство? Конечный автомат или совокупность конечных автоматов.
>>
>>*Любое* цифровое устройство есть совокупность конечных автоматов.
>
>>Утверждение неверное.
>
>Верное, верное. Любое цифровое утсройство есть определённая комбинация элементов логики и памяти. То, что любой из этих элементов есть конечный автомат - тривиально. Отсюда так же тривиально следует выделенное утверждение.

Нет, неверно - есть ещё время работы. И есть операция "предел" при времени, стремящемся к бесконечности. А любая экспонента очень быстро в таковую превращается и на практике. Так что число состояний и переходов у многих алгоритмов будет стремиться к той же бесконечности. В итоге диаграмма переходов в пределе потребует бесконечного времени на отрисовку - при том, что сама программа будет вполне конечна (счётное число строк). Что не соответствует определению конечного автомата. И это даже не учитывая вполне так реального "аппаратного сбоя", что может поставить систему в неопределённое состояние и не учитываться в нормальных системах не имеет права.

Отмечу - ограниченность множества данных на входе не постулируется и не лимитируется. Плюс самомодифицируемость кода тоже никто не отменял. Переход данных в код тоже проблем не представляет. Откуда тогда *конечный автомат*?

От kinetic
К Грозный (31.08.2006 03:56:06)
Дата 31.08.2006 04:31:31

Re: [2СанитарЖеня] кибернетику,

>>>>Что есть любое цифровое устройство? Конечный автомат или совокупность конечных автоматов.
>>>
>>>*Любое* цифровое устройство есть совокупность конечных автоматов.
>>
>>>Утверждение неверное.
>>
>>Верное, верное. Любое цифровое утсройство есть определённая комбинация элементов логики и памяти. То, что любой из этих элементов есть конечный автомат - тривиально. Отсюда так же тривиально следует выделенное утверждение.
>
>Нет, неверно

С каким из трёх последних предложений Вы несогласны?

> - есть ещё время работы.

Причём тут время? Конечный автомат может рассматриваться на любом промежутке времени, от этого он не перестаёт быть таковым.

> И есть операция "предел" при времени, стремящемся к бесконечности.

Предел чего?

> А любая экспонента очень быстро в таковую превращается и на практике.

Экспонента чего?

> Так что число состояний и переходов у многих алгоритмов

Не надо за алгоритмы. Мы говорим за цифровые устройства.

> В итоге диаграмма переходов в пределе потребует бесконечного времени на отрисовку

Дайте сначала определение "диаграммы переходов" - и определение всем используемым сущностям.

> при том, что сама программа будет вполне конечна (счётное число строк).

Противоречивое утверждение.

> И это даже не учитывая вполне так реального "аппаратного сбоя", что может поставить систему в неопределённое состояние и не учитываться в нормальных системах не имеет права.

Наличие сбоев вполне описывается формалистикой конечных автоматов. Вводятся "сбойные" состояния и расширяется входной алфавит (для "вброса" сбоев), ну и расширяется матрица переходов.

>Отмечу - ограниченность множества данных на входе не постулируется и не лимитируется.

Дайте пример хотя бы одного цифрового устройства с неограниченностью входного алфавита.

> Плюс самомодифицируемость кода тоже никто не отменял. Переход данных в код тоже проблем не представляет. Откуда тогда *конечный автомат*?

Понятие "код" вообще бессмысленно для конечного автомата. При интерпретации компьютера как конечного автомата, весь "код" плюс все "данные" (в том числе в регистрах ЦПУ) суть ОДНА точка в огромном пространстве состояний. При модификации кода (как и при модификации данных, как и при переходе ЦПУ на очередную инструкцию) происходит переход в какую-то другую точку.
От Грозный
К kinetic (31.08.2006 04:31:31)
Дата 31.08.2006 14:15:05

Re: [2СанитарЖеня] кибернетику,

>>>>>Что есть любое цифровое устройство? Конечный автомат или совокупность конечных автоматов.
>>>>
>>>>*Любое* цифровое устройство есть совокупность конечных автоматов.
>>>
>>>>Утверждение неверное.
>>>

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

Т.е. если придираться по мелочам, то можно придумать железную чуда-машину, которая реализует простую ОРФ или недетерминистскую Сеть Петри. Пользы от ней никакой не предвидится, в силу её чудесатости. Да и от дальнейшего спора тоже. Завяжем на этом. Вы правы с практической точки зрения - практическое *железо* описывается КА и точка. С программами ещё есть небольшой резон поизвращаться, с железом - пока нету.

Несколько мелких замечаний:

>Дайте пример хотя бы одного цифрового устройства с неограниченностью входного алфавита.

На входе - термометр. Потом АЦП. Микрофлуктуации броуновского движения будем мерять, например. Последовательность случайна (если вы только не сосчитали импульсы и скорости всех атомов во Вселенной). Будет или нет след. показание АЦП считаться всё этой же буквой алфавита или нет будем определять по другому термометру. Любая другая термодинамическая величина - давление, например, или скорость ветра, влажность - тож сойдёт. Подобного типа дивайсы используют и в банках и в физике для счёта методом Монте-Карло, например - гугл hardware random generator (вот например - http://www.ciphersbyritter.com/RES/NOISE.HTM ).

А данные эти будем интерпретировать не просто как пассивные данные, а как команды (самомодифицируемость кода). В ПЛМ-ки будем их зажигать по ходу своей же работы. Обобщённая Рекурсивная Ф-ция в железе получится.

>Наличие сбоев вполне описывается формалистикой конечных автоматов. Вводятся "сбойные" состояния и расширяется входной алфавит (для "вброса" сбоев), ну и расширяется матрица переходов.

Нет, не описывается - только в приближении. Начнём с того, что система со сбоем недетерминирована по времени. Т.е. по оси времени её двигать нельзя. КА - можно. А "расширение матрицы сознания машины" закончится той самой бесконечностью переходов, обрывать которую оператору придётся рубильником "вкл/выкл" в пропущенных матрицей случаях. Опять-таки, только для неограниченного по времени ввода.

>Понятие "код" вообще бессмысленно для конечного автомата.

Да с чего бы это? Код описывает переходы между состояниями. Размер кода пропорционален количеству переходов. Если случайные данные со входа переводятся в программу и исполняются как код, то вся входная последовательность становится программой. При неограниченности размера входной последовательности размер кода неограничен, отсюда с очевидностью следует, что число переходов (да и самих состояний - оно ведь в память целиком влазить не обязано, мы состояние можем считать/хранить по частям) растёт как ф-ция времени, которое неограничено, значит число переходов тоже неограничено и бесконечно растёт в пределе по времени, стремящемся к бесконечности, значит КА перестаёт быть КОНЕЧНЫМ по определению - число переходов бесконечно... Ну неохота дальше писать - полистайте А.П.Ершова, Кнута, про ОРФ - другого Ершова, Ю.Л. , там всё это есть, если интересно. Подобным же образом и число состояний алгоритма чуть более другого класса тоже уходит в бесконечность - опять-таки, в литературе имеется.

От kinetic
К Грозный (31.08.2006 14:15:05)
Дата 01.09.2006 02:08:37

Re: [2СанитарЖеня] кибернетику,

>>Дайте пример хотя бы одного цифрового устройства с неограниченностью входного алфавита.
>
>На входе - термометр. Потом АЦП.

После дискретизации сигнала имеем N бит, т.е. размер входного алфавита равен 2^N. Никакой бесконечности.

>>Наличие сбоев вполне описывается формалистикой конечных автоматов. Вводятся "сбойные" состояния и расширяется входной алфавит (для "вброса" сбоев), ну и расширяется матрица переходов.
>
>Нет, не описывается - только в приближении. Начнём с того, что система со сбоем недетерминирована по времени. Т.е. по оси времени её двигать нельзя. КА - можно.

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

> А "расширение матрицы сознания машины" закончится той самой бесконечностью переходов, обрывать которую оператору придётся рубильником "вкл/выкл" в пропущенных матрицей случаях.

... говорили о конечных автоматах, а у Вас уже проблема останова...

>>Понятие "код" вообще бессмысленно для конечного автомата.
>
>Да с чего бы это? Код описывает переходы между состояниями. Размер кода пропорционален количеству переходов. Если случайные данные со входа переводятся в программу и исполняются как код [...] перестаёт быть КОНЕЧНЫМ по определению - число переходов бесконечно

Даже если такой "конченный" автомат позволит всю матрицу переписывать, то общее число матриц всё равно остаётся конечным, т.е. рано или поздно будет попадание на ту же матрицу, то же состояние и тот же входной символ - и всё пойдёт по кругу. Да и вообще "перезаписываемая матрица" есть просто неявное задание конечного автомата с жёсткой матрицей большего размера. Вы что сказать-то хотели?
От Грозный
К kinetic (01.09.2006 02:08:37)
Дата 01.09.2006 03:56:07

Re: [2СанитарЖеня] кибернетику,


>После дискретизации сигнала имеем N бит, т.е. размер входного алфавита равен 2^N. Никакой бесконечности.

Это ещё не слово, а только его часть. Длина слова кодируется другим источником - я это подчеркнул в пред. сообщении. Есть ненулевая вероятность получить слово произвольной длины. Прочтите внимательно.

>Входная последовательность может зависит от времени сама по себе, без участия автомата, т.е. временная трансляция невозможна в общем случае.

Конечно. Следовательно, это не КА - в общем случае. О чём и разговор.

>... говорили о конечных автоматах, а у Вас уже проблема останова...

Это связано. Жёсткий Останов появляется тогда, когда модель в виде КА перестаёт описывать действительность.

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

Нет. См. в начале. С чего вы взяли, что входное и выходное мн-во - ограничены? Ещё раз подчеркну - неограничены. Это важно.

От kinetic
К Грозный (01.09.2006 03:56:07)
Дата 01.09.2006 15:34:10

Re: [2СанитарЖеня] кибернетику,

>>После дискретизации сигнала имеем N бит, т.е. размер входного алфавита равен 2^N. Никакой бесконечности.
>
>Это ещё не слово, а только его часть. Длина слова кодируется другим источником - я это подчеркнул в пред. сообщении. Есть ненулевая вероятность получить слово произвольной длины. Прочтите внимательно.

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

>>Входная последовательность может зависит от времени сама по себе, без участия автомата, т.е. временная трансляция невозможна в общем случае.
>
>Конечно. Следовательно, это не КА - в общем случае. О чём и разговор.

С какого перепугу?

>>... говорили о конечных автоматах, а у Вас уже проблема останова...
>
>Это связано. Жёсткий Останов появляется тогда, когда модель в виде КА перестаёт описывать действительность.

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

>>Даже если такой "конченный" автомат позволит всю матрицу переписывать, то общее число матриц всё равно остаётся конечным, т.е. рано или поздно будет попадание на ту же матрицу, то же состояние и тот же входной символ - и всё пойдёт по кругу.
>
>Нет. См. в начале. С чего вы взяли, что входное и выходное мн-во - ограничены? Ещё раз подчеркну - неограничены. Это важно.

С того, что построить шину входную или выходную бесконечной пропускной способности невозможно физически. И не для цифрового устройства, а вообще.
От Грозный
К kinetic (01.09.2006 15:34:10)
Дата 01.09.2006 19:15:12

Re: [2СанитарЖеня] кибернетику,


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

С вами дискуссию заканчиваем. Читайте литературу. А ещё вам бы теорию кодирования открыть для себя.

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

Мимо таза. В библиотеку.
От kinetic
К Грозный (01.09.2006 19:15:12)
Дата 02.09.2006 00:24:07

Ожидаемо.

>С вами дискуссию заканчиваем. [...] В библиотеку.

После того, как Вам подробно разъяснили Ваши ошибки, у Вас вместо внятных возражений - раздувание щёк.
От Грозный
К kinetic (02.09.2006 00:24:07)
Дата 02.09.2006 09:03:30

Re: Ожидаемо.

>>С вами дискуссию заканчиваем. [...] В библиотеку.
>
>После того, как Вам подробно разъяснили Ваши ошибки, у Вас вместо внятных возражений - раздувание щёк.

Никаких ошибок вы мне не разъяснили, а всего лишь расписались в своем полном незнании вопроса.

Что и сделало продолжение содержательной дискуссии бессмысленной.

Для вас будет чрезвычайно полезным открыть существование неограниченных грамматик и алфавитов - помимо алфавита на обложке азбуки за 1 класс. Впрочем, до библиотеки вы, похоже, не дойдёте - распущенные перья помешают.
От kinetic
К Грозный (02.09.2006 09:03:30)
Дата 02.09.2006 20:03:02

Нда

В дискуссии о цифровых устройствах, заявляем (правильно):

> практическое *железо* описывается КА и точка

Потом говорим, в той же дискуссии:

> существование неограниченных [...] алфавитов

Случай, видимо, клинический.
От Грозный
К kinetic (02.09.2006 20:03:02)
Дата 03.09.2006 10:11:40

Re: Нда

>В дискуссии о цифровых устройствах, заявляем (правильно):

>> практическое *железо* описывается КА и точка
>

>> существование неограниченных [...] алфавитов

Замечу, что неограниченные алфавиты, ОРФ, самомодификация кода и пр. экзотика никак не связаны с практическим железом - тем, что реально проектируется и идёт в серию, а не в виде упражнения для ума.

Хотя Сеть Петри можно в железе сделать (насколько знаю, никто не делал ещё) и это может иметь вполне прикладное значение для машинного зрения, например. Всю эту экзотику я привёл как пример существования совершенно непрактического железа, никак неописуемого КА. Чисто из буквоедства.

>Случай, видимо, клинический.

Ну вашему врачу виднее - попросите у него удвоить дозу.

Оставили бы вы личные наезды для своей песочницы, ага?
От kinetic
К Грозный (03.09.2006 10:11:40)
Дата 03.09.2006 18:24:19

Устойчивая симптоматика

[...]

> насколько знаю, никто не делал ещё

[...]

> я привёл как пример существования
От Оккервиль
К Грозный (31.08.2006 14:15:05)
Дата 31.08.2006 14:28:58

Уточнение, незначительное

>Любое цифровое устройство есть совокупность конечных автоматов

На деле - реализует совокупность КА.

В практике проектирования приходится учитывать наличие и значимость во времени переходных процессов внутри цифрового устройства. При использовании троичной логики эти вещи учитывать значительно легче. В результате время работы без сбоев чуть ли на порядок больше. И надёжность тоже. ИМХО.