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