On incomparability of interpretation algorithms of typed functional programs with respect to undefined value

В данной работе рассматриваются интерпретаторы типизированных функциональных программ. Алгоритм интерпретации основан на подстановках, $\beta$-редукции и канонической $\delta$-редукции. Основная семантика типизированных функциональных программ есть функция с неопределенными значениями аргументов, которая является главной компонентой ее наименьшего решения. Если значение основной семантики для некоторых значений аргументов есть неопределенность, то алгоритм интерпретации либо останавливается со значением $\bot$, либо работает бесконечно. Показано, что семь известных алгоритмов интерпретации являются попарно несравнимыми относительно неопределенного значения. Это следующие алгоритмы: FS (полной подстановки), PES (параллельной внешней подстановки), LES (левой внешней подстановки), PIS (параллельной внутренней подстановки), LIS (левой внутренней подстановки), ACT (активный алгоритм), PAS (пассивный алгоритм).