The Lyons Family Website  
Introduction to Turing MachinesLet's take a short tour of Turing machines. A Turing machine can be thought of as a primitive, abstract computer. Alan Turing, who was a British mathematician and cryptographer, invented the Turing machine as a tool for studying the computability of mathematical functions. Turing's hypothesis (also known has Church's thesis) is a widely held belief that a function is computable if and only if it can be computed by a Turing machine. This implies that Turing machines can solve any problem that a modern computer program can solve. There are problems that can not be solved by a Turing machine (e.g., the halting problem); thus, these problems can not be solved by a modern computer program. A Turing machine has an infinite tape that consists of adjacent cells (or squares). On each cell is written a symbol. The symbols that are allowed on the tape are finite in number and include the blank symbol. Each Turing machine has it's own alphabet (i.e., finite set of symbols), which determines the symbols that are allowed on the tape. The Turing machine has a tape head that is positioned over a cell on the tape. This tape head is able to read a symbol from a cell and write a new symbol onto a cell. The tape head can also move to an adjacent cell (either to the left or to the right). A Turing machine has a finite number of states, and, at any point in time, a Turing machine is in one of these states. A Turing machine begins its operation in the start state. A Turing machine halts when it moves into one of the halt states. When a Turing machine begins running, it is in its start state and its tape head is positioned over one of the cells on the tape; the symbol on this cell is the current symbol. The operation of a Turing machine proceeds as follows:
It's fairly easy to create a Turing machine that converts a string on the tape from lower case to upper case. However, for many simple tasks that can be performed with a few lines of Java or C, it's difficult and tedious to create Turing machines that performs these tasks. For example, many college students find it challenging to create a Turing machine that multiplies two numbers. For more information about Turing machines and Alan Turing, please visit the following web sites:
Powered by Turing Machines :) 

Last modified: January 12, 2022. Copyright © 2022. Robert C. Lyons. All rights reserved. 