CrazyEngineers
CrazyEngineers

  • What is a turing machine ?

    Morningdot Hablu

    Member

    Updated: Oct 8, 2024
    Views: 1.1K
    hello friends,
    Anybody have some idea about what a turing machine is ?
    Where it is used ?
    :smile:
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • Pensu

    Member • Jul 22, 2010

    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.
    Are you sure? This action cannot be undone.
    Cancel

  • Morningdot Hablu

    Member • Jul 22, 2010

    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 ?
    Are you sure? This action cannot be undone.
    Cancel

  • Pensu

    Member • Jul 22, 2010

    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.
    Are you sure? This action cannot be undone.
    Cancel

  • sushant005

    Member • Jul 22, 2010

    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.
    Are you sure? This action cannot be undone.
    Cancel

  • sushant005

    Member • Jul 22, 2010

    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?
    Are you sure? This action cannot be undone.
    Cancel

  • arunravindran

    Member • Aug 1, 2010

    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.
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register