Results 1 to 6 of 6

Math Help - Turning machine decidable or not

  1. #1
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Turning machine decidable or not

    Given
    Code:
    M = {<A> | A is  DFA and L(A) = empty set  }
    and <A> is some encoding of machine A
    Is M decidable?

    Can someone work with me on how to solve these kinds of problems. This is example problem. We can walk trought similar problems. All online examples seems to be too abstract.
    help would be much appreciated

    thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    537
    Thanks
    10

    Re: Turning machine decidable or not

    You only need to construct a TM that decides on a ...null language!

    So, regardless of input X, the DFA B for the complementary input, will obey L(compliment of X)=...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: Turning machine decidable or not

    hi
    thanks for response
    how do you answer these questions in general.
    i know DFA for empty is just machine with one state which is final as well
    i am just confused how to build these TM . How do you use universal machine in these kinds of questions?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,326
    Thanks
    1297

    Re: Turning machine decidable or not

    By the way, it is "Turing machine" (named for Alan Turing), not "turning".
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: Turning machine decidable or not

    Yes thank you
    I am sorry about that
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Turning machine decidable or not

    Many questions about DFAa are decidable because finite automata have finitely many instructions and finite memory, so they can be exhaustively explored. For example, to check if an automaton does not accept any words, one needs to follow all possible paths starting from the initial state and make sure that one cannot arrive at the accepting state. So this is a graph reachability problem.

    To understand these things, the best thing is to read a good textbook, such as Elements of the Theory of Computation by Lewis and Papadimitriou. Feel free to post other questions here as well.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. slot machine
    Posted in the Statistics Forum
    Replies: 3
    Last Post: December 1st 2012, 06:28 AM
  2. Enigma machine
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 27th 2011, 10:35 PM
  3. Post Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 8th 2010, 02:53 PM
  4. Replies: 11
    Last Post: August 8th 2010, 02:31 AM
  5. atwood machine
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: February 7th 2009, 10:49 AM

Search Tags


/mathhelpforum @mathhelpforum