Definition of Tuning Machine
  1. A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected. A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −
    Q is a finite set of states
    X is the tape alphabet
    ∑ is the input alphabet
    δ is a transition function
    δ : Q × X → Q × X × {Left_shift, Right_shift}.
    q0 is the initial state
    B is the blank symbol
    F is the set of final states
  2. For Example tuning machine for anbn:
  3. NOTE1: 1)if a string is not in the langauge then you are going to hit dead configuration (configuration not defined for that input value) therefore turing machine will halt in non final state.So string wiil not be accepted. 2)we need not define every configuration like in DFA. 3)TM can be used as transduser of 1's complement, transduser of 2's complement,adder,comparator.
  4. NOTE2: writing complex TM by using these bsic TM which can do addition and comparison we can implement any mathematical function.TM is mathematical complete.
  5. Non Halting turing machine:

Contributor's Info

Created: Edited:
0Comment