Идеи

[HumsterProgrammer]

Как владелец репозитория, воспользуюсь им как площадкой для теоретических рассуждений)
Когда размышлял о задачах и в целом структурах, стали интересны следующие вопросы:

• есть ли какие-то работы, посвященные минимальной выразимости программы или распознавателя? Я помню про оценку минимального числа состояний ДКА, НКА, вроде даже про VPL было(теорема Майхила-Нероде). А есть ли развитие этих идей на более общие системы - например минимальная выразимость программы.
• Когда исследовали PDA задался вопросом, что будет если вместо стека будем использовать какие-то другие накопляющие структуры. Например, очередь, очередь с приоритетом, отсортированную очередь. Как изменится выразимость структур? Первое, что заметил, что с помощью очереди можно спокойно разбирать классический ${a^nb^nc^n}$ язык. Даже нашел информацию про тьюринг-полноту такой структуры. Рассматривал ли кто-то свойства подобных систем и причины их свойств?

Был бы рад, если бы направили меня на какие-то размышления, или подсказали, куда можно начать копать.

[TonitaN]

1. Как только ЯП становится алгоритмически полным, выразимость (длина программы) в разных ЯП оказывается отличающейся на константу - длину интерпретатора =) Поэтому такой вопрос очень часто задаётся про ограниченные языки и почти не задаётся про рекурсивные языки, допускающие универсальную функцию.
   Но уже про VPL вопрос не тривиальный - классы эквивалентности по Майхиллу-Нероде описывают структуру минимального блочного автомата, а не минимального автомата в целом. А уж построение минимального PDA и вовсе задача неразрешимая. В целом, обычно вопрос минимальной выразимости не тьюринг-полного языка, если он хоть как-то разрешим, связан с теорией представлений полугрупп с соотношениями (например, в контекстно-свободном случае соотношения могут быть инволюцией). Если есть вопросы к конкретному классу языков, могу поискать ссылки.

2. Про очередь и два стека (деки) да, сразу же получается тьюринг-полнота. Сейчас на практике (в анализе программ) чаще всего не меняют структуру памяти как структуры данных (т.к. очень легко получить сразу тьюринг-полную модель), а шаманят с действиями на переходах (рассматривая так называемые расширенные автоматы, ENFA) и со структурой данных, подаваемой на вход автомату. Но бывает и экзотика - автоматы со стеками стеков (nested stack automata), они уже распознают лишь ограниченный класс языков. И в принципе, там огромное количество ещё не решённых задач. Когда-то я рассматривала вычислительные возможности префиксных грамматик с аналогами стеков стеков.
   А вот короткий обзор, что получится, если в PDA разрешить разные действия со стеком:
   https://esolangs.org/wiki/Extended_pushdown_automata

[HumsterProgrammer]

Спасибо большое. Ознакомлюсь более подробно чуть позже

[TonitaN]

Если интересуют конкретные формализмы и проблемы их анализа, - всегда рада поискать информацию (если не знаю такой) и обсудить.

И мы никуда не спешим, как минимум в 6 семестре =)

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

[HumsterProgrammer]

Снова вернусь с темой того, насколько отличаются различные языки программирования и алгоритмы на них, только в этот раз задамся вопросом похожести двух исполнителей друг с другом.
Я о этой идее задумался после ознакомления с слайдами семинара в Переславле. А именно доклада "Известное преимущество эффективности операционной семантики Рефала и её связь с распознаванием симметрии слов". Мне показалось достаточно интересным эффект, что распознать палиндром на рефале можно за линейную сложность, когда для решения той же задачи точно известно что достигается квадратичная сложность.

Получается разные исполнители имеют разную эффективность в решении тех или иных задач.

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

Вместе с тем очень интересно было покопаться с эзотерическими языками программирования вроде Malbolge. Как я понял, с ним все очень сложно) И например, программа на этом языке может потребовать уже много лишних действий, чтобы просто вывести Hello,World. Возможно я здесь путаю сложность реализации алгоритма в командах исполнителя и сложность самого исполнителя.

Пока я даже не знаю как конкретно сформулировать эту мысль, и вроде как поисковик сильно много информации по этой теме не нашел, но я решил все же оставить записанной эту мысль

[TonitaN]

В принципе, идея, что разные структуры данных - представления данных - порождают разные сложности алгоритмов, преподносится ещё на первом курсе на АиСД: никто же не удивится, если узнает, что строку, представленную массивом, можно проверить на палиндром за линейное время, а односторонним списком - уже нельзя. Поэтому безусловно важно, какое дефолтное представление данных заложено в том или ином языке программирования (особенно, если оно довольно жёсткое, как в Рефале или Лиспе). От этого сильно зависит сложность решения задач на нём.
Другой вопрос - симуляция теоретических моделей. Если бы ещё они существовали подо все существующие ЯП)) В частности, на самом деле теоретическая модель вычислений, соответствующая Рефалу, если и существует, то крайне малоизвестна. Поскольку в Рефале могут встретиться повторные переменные типа выражение, да ещё и, если интерпретатор достаточно умный, он может их обработать за линейное время. Например, такую: e.x 'a' e.x - просто посчитав длину сопоставляемой строки и прогнав цикл по двум половинам этой строки как массивам. Ближайшая классическая модель вычислений - алгорифмы Маркова, - в такое не умеет, но достаточно адекватно передаёт сложность сопоставления с образцами с одной открытой переменной.
Ещё легко заметить, что некоторые естественные модели вычислений неважно симулируются той же одноленточной машиной Тьюринга, так, если ДКА - это её частный случай, то уже симуляция PDA потребует квадратичной "беготни за край ленты" для отслеживания стека (или второй ленты, что проще - но симулирование такой машины на одноленточной происходит ценой увеличения времени до квадратичного, так что здесь сложность перемещается как раз в эту симуляцию). Однако относительно самых общих классов разные модели вычислений демонстрируют удивительную устойчивость: скажем, лямбда-исчисление определяет класс P так же, как и машины Тьюринга (с алгорифмами Маркова это показать и того проще). Поэтому, кмк, Malborge тоже должен сохранять этот P класс, невзирая на нестандартную операцию циклического сдвига и странную тернарную операцию (но, насколько я вижу, являющуюся аналогом "штриха Шеффера" в троичной логике). Другое дело, что "сохранять" его он может большой ценой - огромным константным множителем, усугублённым ещё и больше чем квадратичным переходом по степени полинома. Конечно, узнать эту цену было бы интересно, - может быть, даже оказалось бы, что не всё так страшно там, и какие-нибудь хитрые лямбды в пределе требуют даже больше ресурсов для симуляции машиной Тьюринга, а особенность Malborge - именно в том, что из-за огромного константного множителя он кажется супер-сложным даже на очень простых программах )