[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhchurch_turing_thesis.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Church-Turing thesis" source: https://www.jemoka.com/posts/kbhchurch_turing_thesis/ --- Anything that can be computed by a reasonable model of computation can also be computed by a turing machine. “Everyone’s intuitive notion of algorithms is a Turing-machine” Note that this is not a theorem: its just a scientific hypothesis because we have no formalization of the “intuitive notion”. multi-tape machines Consider: would this give us something stronger? as in, we modify our transition function as simultaneously operating on all tapes \begin{equation} \delta : Q \times \Gamma^{k} \times \qty{L, R}^{k} \end{equation} theorem: every multi-tape TM is actually a single-tape TM. lay your three inputs into your tape, separated by a sharp duplicate your symbol set, each of which to include something which would mark “our head is here” we simply now just run one move on each tape, and moving all the way to the left