Между прочим, на основании вопроса @Fancryer — мне любопытно, есть

Question

Между прочим, на основании вопроса @Fancryer — мне любопытно, есть

ли какие-то практически полезные меры вычислительной мощности (в смысле computational complexity) для реальных машин, с ограниченными ресурсами (и можно даже для конечного размера входа)?

Т.е. теоретически-то все они эквивалентны конечным языкам / Deterministic acyclic finite state automaton, но толку от этого на практике никакого нет, а разница всё же очень даже есть.

К примеру, если известно, что есть:
a) интерпретатор конечных автоматов и
b) интерпретатор любого "обычного" PL,
и каждому предоставлены одинаковые конечные ресурсы, то очевидно, что с помощью (b) получится распознать гораздо большее подмножество языка корректно вложенных скобок, чем с помощью (a).

Есть у кого-то идеи, как могут называться такие меры (или где бы поискать или спросить)?

#compilerdev #it #programming #russian

0

14.09.2023

3 ответов

33 просмотра

Yaroslav Schekin Автор вопроса

Нет, я так и не понял. :( Вы можете показать, как это применить для DFA против RAM/MT (или любой другой "классической" машины) с любым конкретным N (размером "памяти для программы и данных") для задачи распознавания этого языка (корректно вложенных скобок)?

0

18.09.2023

Yaroslav Schekin Автор вопроса

Лимон Цитрусовый
Я тут подумал. Любая полная проверка множества так...

> Следовательно, все такие алгоритмы будут иметь четкую иерархию. Вы бы лучше показали, как на практике применить Вашу идею (потому что я её так и не понял)... > имеет смысл сравнивать только производительность таких машин Эээ... меня вообще не интересовала производительность каких-либо машин (пусть они хоть все 2ⁿ шагов используют, если у них n бит ресурсов). Интересовала только мощность тех подмножеств языков, которые они способны распознавать.

0

22.09.2023

Лимон Цитрусовый · Accepted Answer

Я тут подумал. Любая полная проверка множества таких скобок, вероятно, должна завершаться проверкой на корректность какого-то подмножества таких скобок (даже минимального). Следовательно, все такие алгоритмы будут иметь четкую иерархию. Следовательно, имеет смысл сравнивать только производительность таких машин, либо ни чего не сравнивать.

185 похожих чатов

Между прочим, на основании вопроса @Fancryer — мне любопытно, есть

3 ответов

Похожие вопросы