How Turing Machines Work

at the turn of the 20th century alongside thinking about the mechanization of physical work people began to ponder the mechanization of mental work one way to think about mental work or mental labor is the process of thinking that unfolds when making difficult decisions which leads one to some state of belief about something and at the time people wondered if complex decision making could be mechanized and only in the rent years has anyone uh allowed their judgment so to speak with regard to making decisions uh be made by a computer instead of by human beings for

example IBM's accounting machines would perform a series of calculations and store the intermediate results allowing it to build on previous results to arrive at final answers in uh in about 2 weeks during which we had maybe a a dozen hours of actual calcul ation we did work that would have taken a man with a desk calculator 100 years and immediately people wanted flexibility in terms of what these machines did so the ability to change the sequence of operations became important at first this was done with plug boards allowing one to reprogram the machine's operation physically

and people began thinking about how far we could take this process embedding a sequence of mathematical and logical operations into a mechanism so that it can think for us Hilbert was famous for challenging the academic Community to think about the possibility of the mechanical process that is automatic machines which could answer questions for example one of his challenges was a machine which could answer yes or no as to whether a given statement about mathematics is true if such a mechanical process existed it would completely automate the work of all mathematicians and at the time calculation

machines were well known of course but thinking machines were not and so the mechanisms of these decision machines weren't yet defined people were still speculating and this is where Alan touring enters the story since childhood he was fascinated with the complex mechanisms behind the human mind touring simplified everyone's conceptions of what physical form these decision machines would actually take and in 1928 he published a historic paper that directly addressed Hilbert's challenges in it he imagines a machine that can do anything any other machine might do known as a universal machine and he begins by imagining

a machine as a human in a box with a pencil and a stack of paper and they are handed a book of instructions to follow so in order to change what this human does you must alter the instructions in the book that's the Deep Insight he had defining Behavior with symbols instead of mechanisms this was a very clever trick at the time so he spends the first 60% of his paper laying out precisely how it would work and what form these written instructions or algorithms would take as follows think of each page in this book

of instructions as a single decision first comes an observation which is the if half of the conditional statement and what the person is observing is precisely where their pencil is pointing in the rough work in our example it's the first symbol of the input he calls this their awareness so they are only ever aware of one symbol [Music] next they look at their instructions and compare the symbol in their memory to a list of possibilities in the First Column to find a match Once A match is found they move on to the second step of

the conditional statement the operation step and what they do here is interesting touring observes that no matter what the instructions are or what language they are in they are only ever going to be writing down symbols on the paper and or moving their attention to some new location and so the last column in the table called next state lists the next page to jump to in this book analogy each page in the book is a new Step touring calls these steps states of the machine and when the next state is arrived at their current awareness

where their pencil is currently pointing is observed again and then they scan to find a match in the the same way once they do they follow the sequence and then jump to the next state and this process continues state after State and so the process of computation is exactly like turning pages in a book and at each page making a decision about what to do next based on where the pencil is pointing on a separate page and note that this book wouldn't be read in the same linear order it's more like a Choose Your Own

Adventure at each page because the sequence in which they flow through the pages or states will depend on the input they receive but eventually this process leads to a final state where they write down an answer and halt or stop and they output their result and that's how it works notice the decisionmaking power of this machine is Stripped Away from the human all of the logic of their behavior is based on how the book or algorithm is designed what we call the program and touring notes that all of these steps could be done with pre-existing

technology we don't need a human as follows for reading symbols off the paper touring imagines a simple scanner head which can move around and read individual symbols one at a time into some form of memory known as a read operation and then it would move to the current state and identify when a value in the First Column matches the scanned symbol and once a match is found it moves over to the operation step and lastly it also contains a printer so it can output symbols given by the instructions known as print operations and that's all

it does read move print over and over and over again and to further simplify this touring reminds us that the book you provide or the algorithm and the rough work could all all be done on one big piece of paper and that paper could be arranged in a long array instead of a 2d sheet leading to his famous simplification of a machine which is essentially a roll of tape and a scanner printer head and any symbolic process performed by a modern computer can be performed by this simple machine touring states that anything his Universal machine

can write down is what we call computable so a computable problem is a problem that a touring machine could be programmed to solve given enough time and space to do it a computer as we know today is a device which can accept information in some form store it process it and produce answers in an acceptable read readable form with this definition of course goes the injunction if we're going to call it a computer that it must be able also to store its own instructions and process them from within the machine and so touring showed that

all the power of machines or the future computers would be based on how you designed the instruction table instead of needing any complex mechanisms inside the machine itself he then turns to the larger questions in the second half of his paper what can or can't be written down by an automatic mechanism is there anything that can't be computed what is UN Inc [Music] computable