Доброе утро. Такой вопрос: есть ли какие-то практически полезные меры вычислительной

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

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

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

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

Существует несколько вещей, которые пришли на память, хотя я не могу сказать, как это ложится на алгоритмические сложности, так что извините, все в одну кучу, что относится к скорости. Latency для конкретных операций CPU, они известны для операций процессора, и для операций с шиной памяти. CLOCK Тактовая частота процессора. Вы не можете выполнить алгоритм быстрее, чем пройдут такты обработки операций, зависящих друг от друга. Branching. Операции алгоритма, которые можно теоретически обрабатывать параллельно, могут обрабатываться быстрее за счет спекулятивного исполнения на нескольких конвеерах. Таким образом, алгоритмы, которые работают без ветвления (branching) исполняются в целом быстрее, так как branching исключает спекулятивное исполнение. SIMD. Это и бренд конкретной технологии, и концептуальное название семейства технологий, когда за одну инструкцию исполняется несколько операций. Типичное применение - операции над компонентами векторов, которые выполняются одной инструкцией. Можно до нескольких десятков элементов обрабатывать таким образом. Где-то рядом лежат битовые операции, позволяющие спекулировать тем фактом, что бинарные числа содержат компоненты - биты. Можно за один ход исполнять операций. Концептуально это тоже SIMD - Single Instruction Multiple Data. Структуры данных, которые используются внутри функциональных элементов. Например, внутри кеша первого уровня есть LRU Cache, или что-то подобное, что влияет на Latency Cache locality - алгоритм исполняется быстрее, если элементы лежат рядом в памяти, что уменьшает latency доступа к соседним элементам одним за одним. По сути, чтобы рассчитать настоящую сложность алгоритма, нужно рассчитать алгоритмичнескую сложность низлежащих алгоритмов и структур, которые обслуживают CPU. Тот же LRU внутри кеша процессора.

Еще забыл важную вещь - существует TPU и Operations per Watt. Существует специфическая теплопроводность материалов, из которых изготавливают процессор, и это ограничение и для тактовой частоты и для степени параллелизма процессора. Например, если вы будете много использовать AVX операции, процессор перегреется и сбросит тактовую частоту. Таким образом, вы не можете закачать в CPU больше ватт, чем может отвести система теплоотведения.

Ну и наконец - соотношение теоретического предела скорости распространения электромагнитных колебаний и размера элементарных узлов процессора - транзисторов. Сейчас транзисторы сопоставимы с характерными размерами атома. Атом это ±1 ангстрем, 0.1 нанометр. Размеры транзисторов (или их частей) это сейчас единицы нанометров, то есть десятки ангстрем, значит там толщина в несколько десятков атомов. Человечество вплотную приблизилось к минимальному размеру деталей процессора, и дальше более плотно расположить их не получится, а значит вступает ограничение по скорости света.

можно расположить больше одного атома в объеме равном "объему атома"

Я не силен, в физике атома, не могу возразить ничего. Наверное можно говорить скорее о характерном расстоянии между атомами в кристаллической решетке или аморфном веществе материала.

Вспомнилась статья “Химии и жизни”, под названием “Давишь его давишь, а оно пухнет!”. Типа под давлением атомы газа “прячутся” в кристаллической решетке металла, и он распухает от этого.

В плане ограниченных ресурсов я (как и любая теория сложности!) имел в виду то, что у машины есть N байт для хранения программы и K байт для данных и т.п., например. Никто не рассчитывает на то, что время в мире внезапно кончится, понимаете? ;) А мне кажется, что Вы как-то так прочитали вопрос...

Хмм, а как сделать структуру меньше размера атома?

Давай начнем с того как ты определяешь размер атома

Как величину порядка шага кристаллической решётки

Ну тогда меняем решетку, радиус меняется🤷🏻‍♂

На какую?

Это детали реализации. Сказать что одна конкретная решетка этот фундаментальное ограничение -- странно

У нас конечное множество решёток

У одной решетки может больше одного минимума энергии