Я настаиваю на несколько другой идеи:
Пусть имеется процессор и оперативная память размера N, соединенная с ним шиной. Невозможно обработать запрос на доступ к ячейке памяти в среднем быстрее чем за полином от логарифма N срабатываний элементарных логических элементов, из которых набрана шина. Если дела внутри процессора намного хуже, то эта оговорка не имеет значения, но в случае специализированных вычислений может иметь смысл так сегментировано организовать память, чтобы в каждом сегменте адресов было поменьше.
Если не для тех, кто пишет программы, то для кого проводились исследования и строилась теория вычислительной сложности? «Глас народа — ...». Оценки сложности всегда даются по отношению к некоторой конкретной вычислительной модели, и тот факт, что народ негодует по поводу применяемой RAM модели с доступом к памяти за ограниченное константой количество ходов машины имеет на самом деле не только расхождение с реальными машинами но и некоторые противоречия с теорией передачи информации. Вот вам задачка:
Пусть имеются конечный набор типов идеальных логических элементов («транзисторов» или схем, реализующих более сложные функции). Можно ли построить, пусть даже из бесконечного числа таких элементов, универсальную вычислительную машину с бесконечным адресным пространством и равномерно ограниченным временем доступа ко всем ячейкам памяти (конечного объема), если все логические элементы тратят ровно один ход на выполнения реализуемой ими функции, а сигнал между ними передается мгновенно?
Заметьте, что я снял все ограничения физического или экономического характера, тем не менее, бьюсь об заклад, что смогу перенумеровать ячейки памяти любой удовлетворяющей условиям машины так, что доступ к ним из начального состояния будет ограничен снизу по количеству шагов логарифмом их номера в моей нумерации.
По всей видимости, с бутылочными горлышками в последнее время борются расширяя тротуары и убирая при этом лишние полосы. Метод действенный, но не самый эффективный: возможно большое количество водителей использовали исключительно широкий участок некоторой дороги, сворачивая с нее задолго до горлышка. Теперь выходит, что этот участок стал перегруженным, даже если никакого горлышка уже нет. Один из способов бороться с горлышком, не сужая дороги перед ним — система раздельных светофоров на каждую полосу перед сужением и физическое разграничение этих полос. Светофоры должны открываться поочередно, пропуская движение по стольким полосам, сколько их (полос) в узком месте.
Пропускная способность дороги тоже не самоцель: можно построить очень широкую дорогу с достаточно медленным движением: в итоге у комиссии в отчетах большая пропускная способность, а водители теряют попусту значительное время. Нужен некоторый компромисс между количеством проезжающих машин и потраченным каждой из них временем. Я немного исследовал вопрос оптимальной транспортной сети в городе и, как тогда мне показалось, неплохой критерий есть экономическая мощность дороги: миграция — это торговые связи, они приносят деньги, а само время прохождения дороги каждой машиной их тратит (заработная плата+амортизация). Если вы градоначальник или хотите жить в экономически развитой стране, то будете (не перед выборами, конечно) оптимизировать именно экономическую мощность дороги, а не скорость или поток в отдельности.
Интересным образом задача поиска оптимальной дорожной сети города оказывается переформулировкой задачи коммутации N источников и N стоков. Когда-то я искал схему оптимальной коммутации, результаты публиковались на хабре в статье «Задача телефонисток», может быть дойдут руки написать и про дороги.
Еще хотелось бы уточнить у авторов вид графика поток-скорость: все-таки наверное сначала рост концентрации хоть и приводит к снижению скорости, но поток при этом должен расти, только при значительном уплотнении поток стремительно падает. Если же график монотонный, как на рисунке, то движение просто не устойчивое и пробки должны образовываться всегда, везде, от каждого чиха любого водителя, а не только в проблемных местах дороги.
Энтропийная мощность марковского передатчика (энтропия Шеннона) — абсолютная не зависящая не от чего величина, применимая всюду, где по крайней мере можно утверждать вероятностный либо статистически устойчивый характер процесса.
К примеру взяв 20 типографских оттисков буквы «а» 15 — буквы «б» и 65 — буквы «в» с помощью энтропийной мощности в отсутствие всякой вероятности Вы можете подсчитать количество различных слов длины 100, составленных из этих оттисков.
Если следовать примеру выше и разбить область значений синусоиды на небольшие участки, то получится, что принимая любое значение кроме крайних, почти равновероятен как переход в состояние с большим значением, так и переход в состояние с меньшим. Выходит, что синусоидальный сигнал, будучи полностью предсказуемым, имеет ненулевую энтропийную мощность в качестве марковского передатчика?
Что касается бинарных последовательностей, до сих еще никто не справились с задачей дать удовлетворительную меру сложности единичного конструктивного объекта в себе, колмогоровская сложность безотносительно машины или языка определена лишь для неограниченно усложняющихся последовательностей таких объектов. Иными словами, если наперед задан объект, то можно предъявить машину, относительно которой его сложность равна нулю, как бы он интуитивно сложен не был, и машину, относительно которой сложность этого объекта будет невероятно большой, даже если он интуитивно прост.
Простите, а какая главная мысль статьи? Второй вопрос — как все-таки строится модель энтропийного передатчика для конкретного процесса, например если процесс на осциллографе — правильная синусоида?
Большое спасибо. Только в этой книге говорится немного о другом. Моя идея была описать вещь, не привлекая никаких заранее сформированных структур вроде фреймов или графовых схем на бумаге — я показал на примере, как сформировать представление о предмете как принципиально новое понятие непосредственно в терминах символьной последовательности.
К тому же, вот мнение автора книги, прямо противоположное моим выводам:
«Строятся ли такие системы фреймов для каждого знакомого нам объекта? Это выглядело бы слишком экстравагантно. Представляется более вероятным, что у человека имеются специальные системы для представления наиболее важных объектов, а, кроме того, множество фреймов для обычно используемых „основных форм“; их сочетания образуют фреймы для новых применений.»
Да, в моей статье и в приведенной вами книге, говорится об одной и той же задаче и о совершенно различных способах ее решения.
Как же вы собираетесь определить формально для машины «уметь» и «личное действие»? Я, в свою очередь, пока имею только догадки на этот счет. Считается, к тому же, правилом хорошего тона производить логические построения при минимальных требованиях: абстракции предмета, места и формы доступны и восприятию машин, напрочь лишенных какой-либо возможности действовать, не то что форм самосознания.
Решив простую задачу, часто удается найти ключ и к задаче посложнее. Даже в том виде, который есть, изложенные методы позволяют справится с вещами вроде револьвера и автомобиля. В законах Максвелла тоже нет соринок и скрытых параметров веселости электрика: именно простота академической базы знаний позволяет быть сложными их практическим приложениям. Цель статьи — как раз раскрыть принципы того, как в условиях отсутствия объективной реальности строится субъективное представление о различных понятиях. «Поваренной книгой» она конечно же не является.
Друзья! давайте во избежания конфликтов и введения читателей в заблуждение, всякий раз, говоря, что что-то есть пересказ, переписка или перепечатка, не ленится и давать ссылку на конкретную публикацию или главу книги. В свою очередь, я снова заявляю, что центральная и идея и все примеры — мои собственные и вряд ли встречались где-то до настоящего момента. Если же Вы предъявите конкретную статью, с ровно такими же мыслями, я буду только рад своему неодиночеству в мире.
Не читайте на завтрак советских газет, и книги советских авторов тоже раньше ужина не стоит, иначе действительно развивается как у Вас впечатление, будто они все открыли, а остальные у них списывают. Кому, по вашему, мир обязан открытию теории информации (пропускная способность каналов с шумом и без)?
Шеннон — не только автор теорий, он еще и автор элегантно написанных, в доступной форме преподносящих даже самые сложные идеи книг. Многие слышали об энтропии: какая-то взявшаяся с неба мера беспорядка из учебников по статистике, так думал и я, пока в его трудах по теории информации мне не попалась глава, раскрывающая всю естественность и изящность этого понятия. Странная история, когда полки магазинов прогибаются под не лучшими пересказами научных идей, первооткрыватели которых со временем становятся рекламной вывеской этого сомнительного товара.
Давайте отметим юбилей, размышляя над какой-нибудь статьей именинника!
Шеннон — ученый, гуманист, популяризатор науки.
Правда, могут возникнуть расхождения, если зонд двигается внутри большого одноцветного пятна и в ряде схожих ситуаций. Я вспомнил, что тоже сначала пытался без лампочек движения
Если среди простых движений нет дальних скачков, то Ваше замечание абсолютно справедливо, когда слово паттерн (устойчивая закономерность) понимается в смысле «цветовая конфигурация части индикаторов цвета».
Простите, что не ответил сразу — счел статью интересно и хотел для начала прочитать. В ней тоже не все утверждения обоснованы: например о длительности вычисления параллельными машинами. Я много занимался этой проблемой и смог привести вычислительную модель, которая логарифмировала время (количество шагов) вычисления стандартных алгоритмов: сортировки, поиска по свойству и обращению к памяти. Эта статья тоже присутствовала на хабре — ее любезно согласилчя разместить из под своего юзернейма, но с моей подписью мой приятель. Редакторы хабра даже помогли по-человечески отверстать текст, но при этом потерялось мое имя. В любом случае, гугл еще ищет «Компьютер из маленьких фей». В другой работе «Задача телефонисток» Вы сможете найти обоснование возможности физической реализации вычислительной машины с такой архитектурой.
В любом случае, большое спасибо, подчерпнул для себя много интересного.
Вы заставляете меня нарушить последовательность изложения идей. По сей день нет пока ничего действенного для обнаружения логических закономерностей в символьных последовательностях. Можете, например, предложить из известных вам на рынке технологий, такую, которая по достаточно большому набору слов некоторого конечноавтоматного языка, смогла бы восстановить за приемлемое время вычислений хорошо описывающий этот язык автомат, или еще лучше: решала эту задачу для КС — языков? Боюсь, ничего подобного пока нет и дело по сравнению с 70-ми годами вряд ли далеко ушло вперед. Все хотят сразу учить машины разглядывать картины, играть в покер и читать стихи, и это часто удается гению создателя программ, однако гению его творений даже примитивные, по сравнению с этими задачами, вещи остаются пока недоступны.
Во введении к первой части я говорил о роли участия описательного языка в процессе восприятия. Кроме того, что в этой работе впервые формализованы и исследованы некоторые абстрактные понятия (к ним прибавятся еще «предмет» и «место»), одним из ее результатов, как вы позднее увидите, является тот, что все эти понятия не могут быть подмечены машиной, если она в явной или скрытой форме не использует достаточно развитый описательный язык и не анализирует свои записи на нем. Изначально вся статья называлась «Языковая природа абстрактных понятий», впоследствии по некоторым соображениям название было изменено.
Я уверен, что много исследователей работали над феноменом восприятия, однако в выбранном мною направлении, скорее всего, еще попыток не было.
Мною не утверждается, что приведенные в статье результаты, как-то сами по себе могут решить какую-то из упомянутых здесь проблем или, тем более, в голом виде применены на практике, однако я имею основания полагать, что эти результаты являются пусть даже малым, но необходимым фрагментом знания на пути к пониманию принципов мышления возможности наделения машин (алгоритмов) способности развитого восприятия и поведения.
Марвин Минский написал вместе с Папертом книгу «Персептроны», если вы ее полистаете, то найдете некоторое обоснование приведенных мною доводов в пользу формализации восприятия.
Близкая к теме обсуждения книга фон Неймана «Теория самовоспроизводящихся автоматов», в ней вы тоже найдете доводы о необходимости применения описательных языков, правда для процесса воспроизведения.
Пусть имеется процессор и оперативная память размера N, соединенная с ним шиной. Невозможно обработать запрос на доступ к ячейке памяти в среднем быстрее чем за полином от логарифма N срабатываний элементарных логических элементов, из которых набрана шина. Если дела внутри процессора намного хуже, то эта оговорка не имеет значения, но в случае специализированных вычислений может иметь смысл так сегментировано организовать память, чтобы в каждом сегменте адресов было поменьше.
Пусть имеются конечный набор типов идеальных логических элементов («транзисторов» или схем, реализующих более сложные функции). Можно ли построить, пусть даже из бесконечного числа таких элементов, универсальную вычислительную машину с бесконечным адресным пространством и равномерно ограниченным временем доступа ко всем ячейкам памяти (конечного объема), если все логические элементы тратят ровно один ход на выполнения реализуемой ими функции, а сигнал между ними передается мгновенно?
Заметьте, что я снял все ограничения физического или экономического характера, тем не менее, бьюсь об заклад, что смогу перенумеровать ячейки памяти любой удовлетворяющей условиям машины так, что доступ к ним из начального состояния будет ограничен снизу по количеству шагов логарифмом их номера в моей нумерации.
Пропускная способность дороги тоже не самоцель: можно построить очень широкую дорогу с достаточно медленным движением: в итоге у комиссии в отчетах большая пропускная способность, а водители теряют попусту значительное время. Нужен некоторый компромисс между количеством проезжающих машин и потраченным каждой из них временем. Я немного исследовал вопрос оптимальной транспортной сети в городе и, как тогда мне показалось, неплохой критерий есть экономическая мощность дороги: миграция — это торговые связи, они приносят деньги, а само время прохождения дороги каждой машиной их тратит (заработная плата+амортизация). Если вы градоначальник или хотите жить в экономически развитой стране, то будете (не перед выборами, конечно) оптимизировать именно экономическую мощность дороги, а не скорость или поток в отдельности.
Интересным образом задача поиска оптимальной дорожной сети города оказывается переформулировкой задачи коммутации N источников и N стоков. Когда-то я искал схему оптимальной коммутации, результаты публиковались на хабре в статье «Задача телефонисток», может быть дойдут руки написать и про дороги.
Еще хотелось бы уточнить у авторов вид графика поток-скорость: все-таки наверное сначала рост концентрации хоть и приводит к снижению скорости, но поток при этом должен расти, только при значительном уплотнении поток стремительно падает. Если же график монотонный, как на рисунке, то движение просто не устойчивое и пробки должны образовываться всегда, везде, от каждого чиха любого водителя, а не только в проблемных местах дороги.
К примеру взяв 20 типографских оттисков буквы «а» 15 — буквы «б» и 65 — буквы «в» с помощью энтропийной мощности в отсутствие всякой вероятности Вы можете подсчитать количество различных слов длины 100, составленных из этих оттисков.
Простите, а какая главная мысль статьи? Второй вопрос — как все-таки строится модель энтропийного передатчика для конкретного процесса, например если процесс на осциллографе — правильная синусоида?
К тому же, вот мнение автора книги, прямо противоположное моим выводам:
«Строятся ли такие системы фреймов для каждого знакомого нам объекта? Это выглядело бы слишком экстравагантно. Представляется более вероятным, что у человека имеются специальные системы для представления наиболее важных объектов, а, кроме того, множество фреймов для обычно используемых „основных форм“; их сочетания образуют фреймы для новых применений.»
Да, в моей статье и в приведенной вами книге, говорится об одной и той же задаче и о совершенно различных способах ее решения.
Давайте отметим юбилей, размышляя над какой-нибудь статьей именинника!
Шеннон — ученый, гуманист, популяризатор науки.
Задача телефонисток
В любом случае, большое спасибо, подчерпнул для себя много интересного.
Во введении к первой части я говорил о роли участия описательного языка в процессе восприятия. Кроме того, что в этой работе впервые формализованы и исследованы некоторые абстрактные понятия (к ним прибавятся еще «предмет» и «место»), одним из ее результатов, как вы позднее увидите, является тот, что все эти понятия не могут быть подмечены машиной, если она в явной или скрытой форме не использует достаточно развитый описательный язык и не анализирует свои записи на нем. Изначально вся статья называлась «Языковая природа абстрактных понятий», впоследствии по некоторым соображениям название было изменено.
Я уверен, что много исследователей работали над феноменом восприятия, однако в выбранном мною направлении, скорее всего, еще попыток не было.
Мною не утверждается, что приведенные в статье результаты, как-то сами по себе могут решить какую-то из упомянутых здесь проблем или, тем более, в голом виде применены на практике, однако я имею основания полагать, что эти результаты являются пусть даже малым, но необходимым фрагментом знания на пути к пониманию принципов мышления возможности наделения машин (алгоритмов) способности развитого восприятия и поведения.
Марвин Минский написал вместе с Папертом книгу «Персептроны», если вы ее полистаете, то найдете некоторое обоснование приведенных мною доводов в пользу формализации восприятия.
Близкая к теме обсуждения книга фон Неймана «Теория самовоспроизводящихся автоматов», в ней вы тоже найдете доводы о необходимости применения описательных языков, правда для процесса воспроизведения.