Date: Fri, 27 Oct 2017 15:00:00 +0000
<p class="p1"><span class="s1">TMs are a model of computation at the heart of algorithmic analysis.<span class="Apple-converted-space"> </span> A Turing Machine has two components.<span class="Apple-converted-space"> </span> An infinitely long piece of tape (memory) with re-writable squares and a read/write head which is programmed to change it's state as it processes the input.<span class="Apple-converted-space"> </span> This exceptionally simple mechanical computer can compute anything that is intuitively computable, thus says the Church-Turing Thesis.</span></p> <p class="p1"><span class="s1">Attempts to make a "better" Turing Machine by adding things like additional tapes can make the programs easier to describe, but it can't make the "better" machine more capable.<span class="Apple-converted-space"> </span> It won't be able to solve any problems the basic Turing Machine can, even if it perhaps solves them faster.</span></p> <p class="p1"><span class="s1">An important concept we didn't get to in this episode is that of a Universal Turing Machine.<span class="Apple-converted-space"> </span> Without the prefix, a TM is a particular algorithm.<span class="Apple-converted-space"> </span> A Universal TM is a machine that takes, as input, a description of a TM and an input to that machine, and subsequently, simulates the inputted machine running on the given input.</span></p> <p class="p1"><span class="s1">Turing Machines are a central idea in computer science.<span class="Apple-converted-space"> </span> They are central to algorithmic analysis and the theory of computation.</span></p>
