Suggest edit — Church-Turing thesis

Title

Name

Note

---
title: "Church-Turing thesis"
type: concept
related: [Turing Machinea]
source: https://www.jemoka.com/posts/kbhchurch_turing_thesis/
confidence: high
status: active
---

Anything that can be computed by a reasonable model of computation can also be computed by a turing machine.
&ldquo;Everyone&rsquo;s intuitive notion of algorithms is a Turing-machine&rdquo;
Note that this is not a theorem: its just a scientific hypothesis because we have no formalization of the &ldquo;intuitive notion&rdquo;.
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 &ldquo;our head is here&rdquo; we simply now just run one move on each tape, and moving all the way to the left