School of Computer Science and Engineering, University of Electronic Science & Technology of China, Chengdu, Sichuan, China

Abstract—Turing-computable issue is important in research of Turing Machine and has significant value in both theory and practice. The paper analyzes Turing-computable issue of non-negative numbers by relational operations(includes greater than, less than and equal) and arithmetic operations(includes add operation, subtract, multiply, divide and modulo). The regulation of computing 1-bit binary number and the carry set(or borrow set) are defined to compute multi-bit binary numbers. Algorithms are described through multi-tape Turing machine. For some operations, the discussion is extended to base-N number system(3≤N≤10). Turing regulation for add operation is used to implement the Turing counter for counting the length of the string on the input tape of the Turing machine.

Index Terms—Turing machine, Turing computable, binary, Turing counter.

[PDF]

Cite: Wenyu Chen, Xiaobin Wang, Xiaoou Cheng, Shixin Sun, "Turing Compute Model for Non-negative Binary Numbers," Journal of Software vol. 5, no. 1, pp. 123-130, 2010.