Revision #345 → #1645 · back to history
addedTuring machine7d82ed612b14
addedTuring completeness6e067a129d79
addedRecursively enumerable languagea8f365116901
addedHalting problem is unsolvablec2156c2f50cd
addedUniversal Turing machine61d996fc6bf8
addedChurch–Turing thesisc06cc3262c73
addedTuring machine componentsa0dae184a73c
addedFormal 7-tuple definitionb2144d162a1f
addedAccepted tape contents6dcd0d53716a
added3-state busy beaver 7-tupleb112b699451d
addedFixed-length tape reduces to LBA or FSMd719ac7da1a0
addedAdding no-shift does not increase power923875e95642
added5-tuple convention (definition 1)e4cf1cad737f
added5-tuple convention (definition 2)cb9934441b70
addedAny Turing table from nine 5-tuples346aba7ca942
addedState formula646b02db2efa
addedComplete configuration8862e2ffe35a
addedInstantaneous descriptione7c7b31cd10b
addedTotal state of busy beaver after 3 moves45505405da49
addedEquivalent models have no more power than UTM0039fd215743
addedTM equivalent to relaxed single-stack PDAd91a5300b84c
addedTM equivalent to two-stack PDA3514f7a11f45
addedTuring-equivalent6731766405e6
addedRead-only right-moving TMs equivalent to DFAs1c5ce3212370
addedSome programming languages Turing complete, others not72f90023b28d
addedANSI C is not Turing complete0b4678952157
addedAutomatic machine vs choice machine1e3224a87846
addedOracle machine (o-machine)3baff701b7a0
addedDeterministic TM mimics nondeterministic TMafa71cbe9ec2
addedExistence of universal machine89b73248af29
addedLogarithmic slowdown of universal multitape TMbd4f1db4f679
addedTMs more powerful than FSMs and PDAs2a6760614eae
addedTM computes anything a real computer canef6da712586e
addedRASP machine model097f757d69aa
addedBinary search faster in RASP modelab0e06fe90de
addedArithmetic model vs Turing model0a646680f375
addedEuclidean algorithm polynomial in Turing model only9566d4cf91b7
addedStrongly polynomial time5563b2114288
addedEntscheidungsproblemace62615b082
addedGandy's five operations of the analytical enginec315778723e6
addedOperations (1),(2),(4) yield Turing-computable functionse26cf7243516
addedComputable function (Turing 1939)385338707f7d
addedEntscheidungsproblem has no solution23fdf93b19e8
addedTuring's second proof: does machine print 0823d9ad301d7