dmitgu

Categories:

Как измерить время "в попугаях"

Я тут выпал из ЖЖ — уже упоминал (в оффтопе записи «Сказки для идиотов — как «лоцман» СССР и его осколков, ведущий к краху»), что занялся (по совету разбирающихся в этом математиков) разбиением своей статьи ( http://psta.psiras.ru/read/CompuStrTheory_08.06.2020.pdf ) на несколько.

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

А время — это подсчёт состояний системы — при этом из каждого состояния вычислительной системы переход к другому состоянию «элементарный». Тогда легко делать оценку — считая любой «элементарный» способ перехода требующим одинакового времени. Взяв за основу «самый долгий» и ошибёшься не сильнее, чем линейно. Есть отличный мультфильм «38 попугаев», который подсказал подход к решению:

Продолжим исследование, начатое теоретиком-Удавом на базе решений Попугая-прикладника, На самом деле, для нужд теории алгоритмов нет разницы какая оценка размера Удава — в 38 попугаев или 100 Слоненков. Конечный список, Слоненок от Попугая по своим размерам отличается линейно и «не зависит от аргументов». 

Поэтому можно смело брать такую оценку Удава: «В пределах 100 друзей Удава». При этом измерять может любой друг и — в разных частях. Но — эксклюзивно для своей части. То есть, если один друг Удава меряет эту часть Удава собой, то измерения другого друга Удава на этой же части не прибавляются к итоговому измерению Удава.

Нам нужны функции перехода от состояния к состоянию «почти» без аргументов и чтобы «почти» это всегда была одна и та же функция. 

В чём же состоят вышеназванные «почти»? 

1. Функции перехода от состояния к состоянию образуют конечный список;

2. Аргументы функций перехода принимают конечное количество значений (это символы или числа в ограниченном диапазоне);

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

4. Для перехода от одного состояния к другому могут исполняться «одновременно» несколько данных функций – независимых по используемым ими аргументам и изменяемым характеристикам состояния.

В общем, исследовал вопрос в этом направлении, вроде стало понятно, как свести вычисления к «элементарным» функциям, но это не совсем тривиальный протокол передачи данных от ячейки памяти к ячейке — когда происходит работа со строкой. 

Фишка в том, что для неограниченного размера строки нет канала передачи данных конечной разрядности. Адрес может быть произвольным. И приходится придумывать «бесконечно-разрядную» архитектуру для моей Машины исполнения компьютерных алгоритмов. И, вроде, придумал. 

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

Error

default userpic

Your reply will be screened

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.