1511随机存取机RAM 2、RAM程序 个RAM程序定义了从输入带到输出带的一个映射。可以对 这种映射关系作2种不同的解释。 解释一:把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前η个方格中读入n个整数 X1 X ,n,并且在输出带的第一个方格上输出一个整数 后停机,那么就说程序P计算了函数fx1,x2…,xn)=y 解释二:把RAM程序当作一个语言接受器。 将字符串S=a1a2an放在输入带上。在输入带的第一个方 格中放入符号a1,第二个方格中放入符号a2…,第n个方格中 放入符号an。然后在第n+1个方格中放入0,作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后,在输岀 带的第一格输出—个1并停机,就说程序P接受字符串S。44 15.1.1 随机存取机RAM 2、RAM程序 一个RAM程序定义了从输入带到输出带的一个映射。可以对 这种映射关系作2种不同的解释。 解释一：把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前n个方格中读入n个整数 x1，x2，…，xn，并且在输出带的第一个方格上输出一个整数y 后停机，那么就说程序P计算了函数f(x1，x2，…，xn )=y 解释二：把RAM程序当作一个语言接受器。 将字符串S=a1 a2…an放在输入带上。在输入带的第一个方 格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中 放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标 志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出 带的第一格输出一个1并停机，就说程序P接受字符串S