补充资料：可计算函数

可计算函数
computable function

　　【补注】‘动作符号”L，R，S分别表示“左移’，“右移”，“不动”(“立定”). 在计算的数学理论(mathemati份1 theo砂(，f‘刃m-putation)一条中可以找到可计算函数的更多的信息.杨东屏译可计算函数，皿pu加ble肠口比皿;~I.c胜~中y皿K叭叫 一个函数，其值可用一事先给定的能行过程或算法(川即月由m)来计算.计算过程的特征性质是事实:问题的未知量可被一确定的事先给的规则和指令由给定初始值逐步计算出来.许多数学里的计算过程的有用例子给出计算过程的直观概念.在20世纪从事的数学基础的一般计划的范围里，要求出现和直观的算法概念不同的精确的算法概念.可计算函数，能行过程和算法的精确定义被D.托lbert，K .G记el，A.Church，5.C.Kleene，E.L.P谓t，A M.Turing及A A MapKoB以不同的形式给出. 建立严格的数学定义的不同道路的一般想法可陈述如下对已知的或可想到的计算过程作了仔细的分析，揭露了这些过程的重要特征，发现了这些过程和它们的特性的适当的数学相似物.这概念的不同方向的实现不是模糊的，且得到数学算法概念的不同形式.算法概念的基本模型是Turing机，部分递归函数，M句卿。B的正规算法及其他形式. T硕ng机(Turing ma比ine).数学中用的算法类似于在分开的行上工作的机器，经过几行后机器可作出回应.T而ng和P份t刻画了抽象机器的概念(见抽象计算机(~puter，abetract))，在其上可模拟计算过程.一个Turing机(或Turing一R万t机)M由下列东西组成: a)一个亨眼字毋寺(finite alPhabe‘)“二(a0，‘”，a。}，其中a，是任意符号;字母表戊的符号的有穷有序的序列称为字母表:上的字;字母表“上的字作为初始问题，中间计算及得到的结果的编码. b)由机器M可能出现的攀夺琴春(elementa斗“tates)的亨尽春(fi”itelis‘)Q={a0，…，‘};ql被认为是M的初始状态，M开始工作时处于此状态;q0是终止状态:若M进人状态q0，则停止运算. “)俘序(Progratn“)，它由若干个单个指令双，组成，其中不，具有形式久马~a*Dq，之一其中0‘i，k‘n，0　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。