Computable stack functions for semantics of stack programs

作者:

Highlights:

摘要

Functions computable on stack machines are studied algebraically. Computable functions N∗ → N∗ are considered as meanings of programs (on stack machines) which cause the content of the stack before execution of the program to be transformed into the content of the stack after its execution. Church's thesis is extended by showing that every computable function N∗ → N∗ can be characterized as a stack function.

论文关键词:

论文评审过程:Received 1 October 1978, Revised 17 April 1979, Available online 2 December 2003.

论文官网地址:https://doi.org/10.1016/0022-0000(79)90024-2