Turing Machine

-
Turing Machine was invented by Alan Turing in 1936 and it is used to accept Recursive Enumerable Languages (generated by Type-0 Grammar).
Turing Machine (Halt State Version) 
 A Turing Machine is a sextuple of the form 7-tuple (Q, T, B, ∑, δ, q0, B, F) where:

  • Q is a finite set of states
  • T is the tape alphabet (symbols which can be written on Tape)
  • B is blank symbol (every cell is filled with B except input alphabet initially)
  • ∑ is the input alphabet (symbols which are part of input alphabet)
  • δ is a transition function which maps Q × T → Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, change the tape symbol (may or may not) and move head pointer to either left or right.
  • q0 is the initial state
  • F is the set of final states. If any state of F is reached, input string is accepted 


A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.
A Turing machine is a general example of a CPU that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine (automaton) capable of enumerating some arbitrary subset of valid strings of an alphabet; these strings are part of a recursively enumerable set. A Turing machine has a tape of infinite length on which it can perform read and write operations.

Comments

  1. bitcoinMay 16, 2019 at 2:33 AM


    Withdraw your cryptocurrency with bitcoin to bank account easily with this site without any kind of taxes or fee. Yes! this is best site for you, even you can exchange your bitcoin with any account in all over the world.

    ReplyDelete

Post a Comment

Popular posts from this blog

Array

-
Image
  An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number. For instance, if we want to store the marks scored by a student in 5 subjects, then there’s no need to define individual variables for each subject. Rather, we can define an array which will store the data elements at contiguous memory locations. · array  marks[5]  defines the marks scored by a student in 5 different subjects where each subject marks are located at a particular location in the array i.e.  marks[0]  denotes the marks scored in first subject,  marks[1]  denotes the marks scored in 2nd subject and so on.
Read more
-
  STACKS in Data Structure A stack is  an abstract data type that holds an ordered, linear sequence of items . In contrast to a queue, a stack is a last in, first out (LIFO) structure. A real-life example is a stack of plates: you can only take a plate from the top of the stack, and you can only add a plate to the top of the stack... Click here to Know more
Read more

Asymptotic notations

-
  Data Structure The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on machine specific constants,  and doesn’t require algorithms to be implemented and time taken by programs to be compared. Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis.  The following 3 asymptotic notations are mostly used to represent time complexity of algorithms. 1) Θ Notation, 2) Big O Notation, 3) Ω Notation. Click here to learn more
Read more