| K带实时图灵机计算能力与图灵机带数的关系 |
| |
| 引用本文： | 戴上平 高丽. K带实时图灵机计算能力与图灵机带数的关系[J]. 计算机与数字工程, 2000, 28(1): 14-16 |
| |
| 作者姓名： | 戴上平 高丽 |
| |
| 作者单位： | 华中师范大学计算机科学系，华中师范大学计算机科学系 武汉 430079，武汉 430079 |
| |
| 基金项目： | 湖北省自然科学基金(98J076) |
| |
| 摘 要： | 本文证明了对任意整数k,至少存在一个语言能被k带实时图灵机接受,但不能被(k—1)带实时图灵机所接受,从而证明了k带图灵机计算能力严格强于(k-1)带实时图灵机。
|
| 关 键 词： | 图灵机 实时图灵机 实时计算 K带 |
On the Power of Real - Time Turing Machine |
| |
| Dai Shangping Gao Li. On the Power of Real - Time Turing Machine[J]. Computer and Digital Engineering, 2000, 28(1): 14-16 |
| |
| Authors: | Dai Shangping Gao Li |
| |
| Abstract: | We show that for any integer K,there is at least one language which is accepted by k - tape real -time Turing machine, but cannot be accepted by a (k-1)- type real - time Turing machine. Therefore, we show the computing capability of k - tape Turing machine is higher than that of (k - 1) type Turing machine. |
| |
| Keywords: | Turing machine Real - Time Turing Machine Real - Time computing |
| 本文献已被 CNKI 维普 等数据库收录！ |
