Panther Tracks

  • Senior Prom - June 9th

  • Buy your prom tickets TODAY

  • Senior Awards Night - June 7th

  • Last Day of School - June 21st

  • Sign Up For Panther Cup - June 5th

Filed under Hobbies, Lifestyles

Computational Model: Turing Machine

https%3A%2F%2Fcommons.wikimedia.org%2Fwiki%2FFile%3AMaquina.gif
https://commons.wikimedia.org/wiki/File:Maquina.gif

https://commons.wikimedia.org/wiki/File:Maquina.gif

Schadel

Schadel

https://commons.wikimedia.org/wiki/File:Maquina.gif

The turing machine is a computational model that was invented in 1936 by Alan Turing to solve the problem of undecidability.

In theory, the turing machine can be used to represent any algorithm computable by a machine. Thus it would follow that a turing complete ( following paragraph ) language can perform any possible computation.

Turing completeness is determined by a computational representation’s or programming language’s ability to simulate a turing machine. Commonly, when determining turing completeness memory limitations are ignored.

The turing machine is constructed of three parts: a tape, a read/write head, and a controller.

The tape is of infinite length, and is divided in compartments. Each compartment can hold a single symbol from the alphabet being used. In modern ( 2018 ) computers, the alphabet would be a one or a zero.

The read/write head is located above a single compartment on the tape. The head contains no memory, but can move up and down the tape. The job of the head is to read and write to the compartment it is located above.

The controller contains a number of states, and provides instructions given a state and an input from what the head reads.

When the turing machine starts computing: the tape starts in some initial condition with some input; the read/write head starts at some initial position; and the controller begins in some state.

From which the machine’s read/write head will read the tape at its own position.

The controller uses its state and the information read from the read/write head to determine lookup a set of instructions to follow. These instructions contain a symbol to write to the tape, a state to change the controller to, and a left or right move for the tape.

First, the read/write head writes the symbol provided from the controller to the tape.

Second, depending on how one conceptualizes the machine, it either: has the tape move one compartment left or right, or the read/write head moves one compartment left or right. Regardless of the conceptualization, the effect is the same; the read/write head is over a different compartment.

Finally, the controller changes to a new state. If the controller’s new state is a halting state, which are predetermined, then the machine halts, and the current tape is the output.

Print Friendly, PDF & Email

About the Writer
Josiah Wolf, Lifestyles, Staff Writer

Josiah has a modest knowledge of economics, formal logic, and TRPGs.

Print Friendly, PDF & Email
Leave a Comment

If you want a picture to show with your comment, go get a gravatar.




Navigate Right
Navigate Left
  • Computational Model: Turing Machine

    Hobbies

    An overview of Category Theory.

  • Computational Model: Turing Machine

    Hobbies

    Programming Paradigms

  • Computational Model: Turing Machine

    Hobbies

    Lambda Calculus: Reduction

  • Computational Model: Turing Machine

    Hobbies

    Lambda Calculus: An Overview

  • Computational Model: Turing Machine

    Hobbies

    How compilers work: an overview.

  • Computational Model: Turing Machine

    Hobbies

    Dungeon Mastery: Political Games, Diplomacy.

  • Computational Model: Turing Machine

    Hobbies

    Dungeon Mastery: Political Games, War and Peace.

  • Computational Model: Turing Machine

    Hobbies

    Dungeon Mastery: Political Games, using Central Tensions.

  • Computational Model: Turing Machine

    Hobbies

    Dungeon Mastery: Preparing to Play, Fronts

  • Computational Model: Turing Machine

    Hobbies

    The techniques and steps to Flintknapping

The World's Greatest Highschool!!
Computational Model: Turing Machine