|
|||||
|
|
| 计算问题的空间难解性 | |
| 引用本文： | 刘传领,宋玉杰,连祥凯.计算问题的空间难解性[J].商丘职业技术学院学报,2003,2(3):15-17. |
| 作者姓名： | 刘传领 宋玉杰 连祥凯 |
| 作者单位： | 1. 商丘职业技术学院,河南,商丘,476000 2. 周口师范学院,河南,周口,466000 3. 郑州市消防支队,河南,郑州,450003 |
| 摘 要： | 在计算问题中有些是不可解的或称难解的 .虽然它们在理论上是可解的 ,但解法需要大量的时间和空间 ,而无法在实践中应用 .计算理论中的空间函数、层次推理、正则运算等都从空间角度论证了计算问题的不可解性即计算问题的难解性 . |
| 关 键 词： | 层次定理 空间 图灵机(Turing) 模拟 可判定性 |
| 文章编号： | 1671-8127(2003)03-0015-03 |
| 修稿时间： | 2003年3月15日 |
The Space hard-processing of the Problem of Computation |
|
| LIU Chuan-ling ,SONG Yu-jie ,LIAN Xiang-kai.The Space hard-processing of the Problem of Computation[J].Journal of Shangqiu Vocational and Technical College,2003,2(3):15-17. | |
| Authors: | LIU Chuan-ling SONG Yu-jie LIAN Xiang-kai |
| Institution: | LIU Chuan-ling 1,SONG Yu-jie 2,LIAN Xiang-kai 3 |
| Abstract: | In the computation problem some are hard -processing,though those can be realized in theory. It will take enormous time or space,and it is hard to practise. We regard them as hard-processing. Space function,hierarchy theorem and regular operation proof that computation problems are hard-processing in the space aspect in the theory of computation. |
| Keywords: | hierarchy theorem space Turing simulation decidability |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |