Introduction to Turing Machines

From Wikiversity

Jump to: navigation, search
Crystal Clear app kaddressbook.png
Please help develop this page

This page was created, but so far, little content has been added. Everyone is invited to help expand and create educational content for Wikiversity. If you need help learning how to add content, see the editing tutorial and the MediaWiki syntax reference.

To help you get started with content, we have automatically added references below to other Wikimedia Foundation projects. This will help you find materials such as information, media and quotations on which to base the development of "Introduction to Turing Machines" as an educational resource. However, please do not simply copy-and-paste large chunks from other projects. You can also use the links in the blue box to help you classify this page by subject, educational level and resource type.
Commons-logo.svg Search Wikimedia Commons for images, sounds and other media related to: Introduction to Turing Machines
Wikimedia-logo.svg Search for Introduction to Turing Machines on the following projects:
Smiley green alien whatface.svg Lost on Wikiversity? Please help by choosing project boxes to classify this resource by:

The concept of Turing machines is one of the founding principles of modern computing. First theorised and then expanded upon by Alan Turing, the concepts of various Turing machines have been adapted to analyse complexity among other things. Turing machines are types of finite state machines.

This page will be describing what determinism and non-determinism are because such material is needed to understand some of the concepts behind Turing machines, even though this work is better suited to be explained in a page about Automata Theory.

Contents

[edit] What is a Turing Machine?

A Turing machine is an abstract concept used to describe a type of machine that, given an indefinte amount of space and time, can be adapted to calculate anything, such as the digits of π or even a whole universe.

A simple Turing machine consists of a tape of a theoretically infinite size consisting of cells, or sections on the tape. Each cell holds on it a symbol, which is written to it by the head, and which midified the current state of the machine.

There is a finite number of symbols that the head can read or write. Any cells to which the head did not write previously is considered to hold the blank symbol, often designated as b. This means that at any point during the execution of the Turing machine, there is an infinite amount of blank symbols on the tape.

The initial state, designated by q0, is the state in which the Turing machine is in at the beginning of execution.

[edit] What Different Types of Turing Machines are There?

There are many different type of Turing machines that are often used to describe certain kinds of execution. The two that are most often used are deterministic and non-determinnistic Turing machines.

[edit] What is a Deterministic Turing Machine?

A deterministic Turing machine, is one that uses the concept of determinism to calculate a solution to a problem.

Determinism is the concept of being only in one state at a given time and determining what the next state will be from that state. In simpler terms, determinism would be being in state q0, and only holding that that state until moving onto the next state, q1. In determinism we would be able to predict without any doubt that the head would move from state q0 to state q1. A Turing machine does not have to even halt, or stop execution, in order for it to be considered deterministic.

[edit] What is a Non-deterministic Turing Machine?

A non-deterministic Turing machine, is one that uses the concept of non-determinism to calculate a solution to a problem.

A non-deterministic Turing Machine differs from a non-deterministic Turing Machine in the sense that a non-deterministic Turing Machine can have several possible states to which it can transition from any given state, qi. One way to think of it would be to think that, given the possibility of choosing from several subsequent states, the non-deterministic turing machine guesses the next iteration that will bring it to a ‘yes’ answer. Put a different way, the non-deterministic Turing machine branches out into holding many states at the same time in a sort of tree fashion until one of the many paths leads it to a ‘yes’ answer. In perspective a non-deterministic Turing machine may, for instance, be in state q0 and then hold both state q_{1_{1}} as one of the branches and state q_{1_{2}} as another branch.

[edit] Other Types of Turing Machines

Retrieved from "http://en.wikiversity.org/wiki/Introduction_to_Turing_Machines"