Отсюда вывод: чтобы сделать алгоритм, который будет выгодно считать только на связке CPU + RAM, нужно подобрать такой класс задач, который:
1. очень хреново параллелится (это поможет только от щёлканья одной задачи параллельно на GPU, но не поможет от того, чтобы запустить их тысячу параллельно),
По первому пункту большой вопрос - а существует ли такой?
Очень хотелось бы чтобы он был. Однако особенность PoW в том, что нужно большое время в работе и очень маленькое время при проверке. Поэтому в обычном понимании "плохо распараллеливаемые алгоритмы" нам не подходят. Например, такой алгоритм PoW как расчет хэша SHA-256 я думаю, что тоже не распараллеливаемый алгоритм, но его просто запускают параллельно с разными параметрами nonce.
В общем-то, успешный подбор/угадывание нонса и определяет "удачливость" майнинга. Полагаю, Вы говорили именно о создании PoW-алгоритма, для которого будет достаточно сложно/невыгодно сконструировать ASIC. Вы предложили использовать некий интерпретатор, вот это хорошая идея. Вычислительные операции алгоритма должны быть заранее неизвестны и задаваться, например, исходя из хеша предыдущего блока.