请输入您要查询的字词:

 

单词 TuringComputable
释义

Turing computable


A function is Turing computable if the function’s value can becomputed with a Turing machineMathworldPlanetmath.

More specifically, let D be a set of words in a given alphabet andlet f be a function which maps elements of D to words on thesame alphabet. We say that f is Turing computable if thereexists a Turing machine such that

  • If one starts the Turing machine with a word wD as theinitial content of the tape, the computation will halt.

  • When the computation halts, the tape will read f(w).

Formally, let Σ be an alphabet and f:Σ*Σ* on words over Σ. Then f is said to be Turing-computable if there is a Turing machine T over Σ (its input alphabet), as defined in this entry (http://planetmath.org/FormalDefinitionOfATuringMachine), such that for any wΣ*,

(s,τw,1)*(h,τf(w),m)

for some m. Here, h is a halt state (either an accept or a reject state), and τw for any word w is defined as the tape description such that the content of the i-th square is the i-th letter of w, and blank everywhere else.

Because of the fact that all types of Turing machines (deterministicMathworldPlanetmath,non-deterministic, single head, multiple head, etc.) all have the samecomputational power, it does not matter which type of Turing machineone uses in the definition.

It is not hard to find examples of Turing computable functions —because Turing machines provide an idealized model for the operationMathworldPlanetmathof the digital computer, any function which can be evaluated by acomputer provides an example.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 16:13:28