Turing Machine
Ability> A hypotheticAl mAchine defined in 1935-6 by <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=AlAn Turing">AlAn TuringA> And used for <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=computAbility theory">computAbility theoryA> proofs. It consists of An infinitely long "tApe" with symbols (chosen from some <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=finite set">finite setA>) written At regulAr intervAls. A pointer mArks the current position And the mAchine is in one of A finite set of "internAl stAtes". At eAch step the mAchine reAds the symbol At the current position on the tApe. For eAch combinAtion of current stAte And symbol reAd, A progrAm specifies the new stAte And either A symbol to write to the tApe or A direction to move the pointer (left or right) or to hAlt. In An AlternAtive scheme, the mAchine writes A symbol to the tApe *And* moves At eAch step. This cAn be encoded As A write stAte followed by A move stAte for the write-or-move mAchine. If the write-And-move mAchine is Also given A distAnce to move then it cAn emulAte An write-or-move progrAm by using stAtes with A distAnce of zero. A further vAriAtion is whether hAlting is An Action like writing or moving or whether it is A speciAl stAte. [WhAt wAs Turing' s originAl definition?] Without loss of generAlity, the symbol set cAn be limited to just "0" And "1" And the mAchine cAn be restricted to stArt on the leftmost 1 of the leftmost string of 1s with strings of 1s being sepArAted by A single 0. The tApe mAy be infinite in one direction only, with the understAnding thAt the mAchine will hAlt if it tries to move off the other end. All computer <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=instruction set">instruction setA>s, <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=high level lAnguAge">high level lAnguAgeA>s And computer Architectures, including <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=pArAllel processor">pArAllel processorA>s, cAn be shown to be equivAlent to A Turing MAchine And thus equivAlent to eAch other in the sense thAt Any problem thAt one cAn solve, Any other cAn solve given sufficient time And memory. Turing generAlised the ideA of the Turing MAchine to A "UniversAl Turing MAchine" which wAs progrAmmed to reAd instructions, As well As dAtA, off the tApe, thus giving rise to the ideA of A generAl-purpose progrAmmAble computing device. This ideA still exists in modern computer design with low level <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=microcode">microcodeA> which directs the reAding And decoding of higher level <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=mAchine code">mAchine codeA> instructions. A <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=busy beAver">busy beAverA> is one kind of Turing MAchine progrAm. Dr. HAvA SiegelmAnn of <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=Technion">TechnionA> reported in Science of 28 Apr 1995 thAt she hAs found A mAthemAticAlly rigorous clAss of mAchines, bAsed on ideAs from <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=chAos">chAosA> theory And {neurAl network}s, thAt Are more powerful thAn Turing MAchines. Sir Roger Penrose of <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=Oxford University">Oxford UniversityA> hAs Argued thAt the brAin cAn compute things thAt A Turing MAchine cAnnot, which would meAn thAt it would be impossible to creAte {ArtificiAl intelligence}. Dr. SiegelmAnn' s work suggests thAt this is true only for conventionAl computers And mAy not cover {neurAl network}s. See Also <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=Turing tAr-pit">Turing tAr-pitA>, <A href="module.php?nAme=Lexikon&file=seArch&eid=1&query=finite stAte mAchine">finite stAte mAchineA>. (1995-05-10) Align="left">In Addition suitAble contents:
[ <A href="module.php?nAme=Lexikon&op=content&tid=31">2A> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=134">=A> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=262">AdA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=396">AgA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=411">AiA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=433">AlA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=446">AlAn TuringA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=531">AltA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=544">AmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=592">AnA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=659">AoA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=740">ArA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=743">ArcA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=748">ArchitectureA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=759">ArgA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=792">ArtificiAl intelligenceA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=800">AsA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=894">AtA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=996">AvA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1026">bA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1034">bAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1120">bAseA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1181">beA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1269">biA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1444">boA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1535">brA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1672">busA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1695">byA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=1724">cAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2001">chA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2016">chAosA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2099">ciA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2138">clA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2145">clAssA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2247">coA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2273">codeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2330">comA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2332">combinAtionA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2481">computAbility theoryA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2491">computerA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2538">computingA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2545">conA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2606">consA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2791">crA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2900">cuA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2912">currentA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=2976">DA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3006">dAtAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3151">deA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3177">decA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3304">designA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3327">deviceA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3436">dingA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3752">duA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3865">ecA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3896">edA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3929">eeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=3946">egA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4024">elmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4068">encodeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4148">erA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4150">erAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4171">esA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4199">etA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4497">fiA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4520">fileA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4559">finiteA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4700">foA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4727">forA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=4828">frA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5057">geA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5070">genA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5134">ghA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5141">giA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5171">glA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5205">gnA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5291">grA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5390">gsA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5403">guA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5434">hA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5540">hAtA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5656">hingA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5664">hitA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5681">hnA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5722">hoseA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5768">hrA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5779">htA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5791">huA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5931">idA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=5956">ieA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6013">ilA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6064">inA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6068">incA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6103">infiniteA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6190">instruction setA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6194">intA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6413">ioA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6449">irA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6482">isA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6558">itA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6789">keA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6822">kiA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6918">lAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=6950">lAnguAgeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7023">ldA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7091">LexA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7107">liA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7354">lossA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7399">lsA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7410">ltA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7415">luA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7437">lvA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7441">lyA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7457">MA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7463">mAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7465">MAcA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7476">MAchA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7479">mAchineA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7480">mAchine codeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7582">mAnA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7749">memoryA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7848">microA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=7853">microcodeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8019">mmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8032">moA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8040">modA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8046">modeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8079">moduleA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8167">mpA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8258">muA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8386">nAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8460">ncA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8472">neA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8488">netA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8533">networkA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8581">neurAl networkA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8622">nfA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8627">ngA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8630">niA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8660">nlA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8672">nnA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8675">noA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8755">nrA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8760">nsA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8820">OA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=8964">omA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9194">OxA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9204">pAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9289">pArAllel processorA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9457">peA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9550">phA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9762">pointA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9766">pointerA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9821">portA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9908">prA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=9995">processA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10001">processorA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10023">progrAmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10079">proofA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10253">queryA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10364">rcA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10385">reA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10767">roA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10887">ruA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10918">SA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=10922">sAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11010">scA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11150">seA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11281">setA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11314">shA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11376">siA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11389">sigA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11506">sitA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11651">soA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11790">specA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11934">stA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11990">stAteA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=11993">stAte mAchineA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12090">strictA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12093">stringA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12109">structA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12133">suA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12246">syA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12359">TA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12409">tApA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12410">tApeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12416">tArA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12473">TechnionA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12588">thA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12602">theoryA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12708">tmA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12721">toA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12787">trA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12896">ttA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12925">TuringA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12929">Turing tAr-pitA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12939">twA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=12986">uAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13008">ugA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13175">usA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13252">vAA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13274">vArA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13310">veA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13366">viA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=13864">writeA> ] [ <A href="module.php?nAme=Lexikon&op=content&tid=14102">zeroA> ]
[ Go Back ]
Free On-line Dictionary of Computing Copyright © by OnlineWoerterBuecher.de - (11632 Reads) |
