What is a turing machine ?

Replies

• 

  Pensu

  Turing Machine was discovered by Alan Turing in 1936. It is basically used in algorithm design. We can match strings using it. It has a head and a stack. It has a push and pop operations.
  We use it when DFA and NFA fails to work. Its a theoretical device.
  
  Correct me if i am wrong.
• 

  Morningdot Hablu

  You are vary correct.
  
  Can you tell me why it is called a logical computing machine and why we said that it has infinite memory capacity ?
  And one more thing where it is used ?
• 

  Pensu

  Its a computing machine because we use it in computation related works like to check a language and we say it has infinite memory capacity because it is a theoretical concept(May be....I am not sure about this...!!).
  
  To understand its working we can take an example. Suppose we have to check a language of type L={a^n c b^n,n>1}. This language will accept all the strings where number of a's is equal to number of b's and they have a c in between of them.
  
  So what turing machine does is it put its head pointer at the first 'a' and pushes it in its stack and moves ahead. It continues to this process till the time it finds a 'c'. After 'c' when it encounters a first 'b', it pop out an 'a' and move ahead on another 'b' repeating same process. After the string finishes it check the stack. If the stack is empty then the particular string is accepted by that particular language, otherwise the string doesn't belong to that language.
  
  Hope this will help.
• 

  sushant005

  Up to what i know turing machine can do what a real computer can do.
  It is very similar to the Finite automaton(DFA and NFA) but with unlimited (infinte ) memory.
  When we are given an string as an input to the turing machine then there exist three possibilities that string may be excepted, rejected or looped.By looping we mean that the machine simply does not halt(stop).It is also not necessarily repeating the same steps in the same way forever.Looping may entail any simple or complex behaviour that never leads to a halting state.
  
  The Turing machines that halt on all inputs never looped. These machines are called deciders because they always make a decision to accept or reject. A decider that recognizes some language also is said to decide that language.
• 

  sushant005

  i think the concept of Turing machine comes into existence when DFA and NFA fails to work.
  There must be some problem which are not solved by Turing machine so my question is, Is there any concept used to solve those problem?
• 

  arunravindran

  Hi guys,
  
  A Turing machine is a theoretical device that manipulates symbols contained on a strip of tape. It was built in 1936 and since then the way computation takes place changed. It starts from the grassroot of computer science i.e. compiler. Its a concept which is very important as far as converting a language written in human readable form to machine readable form. All the symbols are accepted or rejected by an infinite set of tape. This machine helped a computer become an "automated" machine.