Thread: Turing machine

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2013
    Posts
    10
    Rep Power
    0

    Turing machine


    Hello!
    1) How would you create a Turing machine that accepts words w formed with the a, b, c letters so that #a(w) + #b(w) != #c(w), where #a(w) means the number of "a" 's from the word w etc.

    Could we use a Turing machine with two tapes to separate on the first tape all the letters of a and b, on the 2nd all the c letters and then to compare the lengths? Is there an easier method?

    2) Turing machine that returns the value of f(n)=2^n-1, if we give it the input n.

    I could use a Turing machine to compute 2^n in this way:
    on the first tape I have the representation of n ( 111111...11 - n+1 times), on the second tape I have 111 = representation of 2, and then on an additional tape, for every 1 in the representation of n, I copy the previous tape, for 2 times. And I generate the number 4. then I copy on another tape the previous tape, 2 times, and I get 2^3 etc. of course, I have to pay attention to the additional 1 from every tape. ( to delete it and then add it again...)

    And then I delete a '1' from the last tape, to get 2^n-1.

    Is it ok, is there an easier method?
    Thank you!
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2013
    Location
    Saint-Petersburg, Russia
    Posts
    236
    Rep Power
    28
    How would you create a Turing machine that accepts words w formed with the a, b, c letters so that #a(w) + #b(w) != #c(w), where #a(w) means the number of "a" 's from the word w etc.
    What you mean by "accept" by the way?

    If it is about switching to the state qY if the word was acceptable and qN if was not, I think the following approach could be used:
    - seek for letter 'a', when found change it to 'x' and rewind to start of the word;
    - seek for letter 'b' to change it to 'x' too - if not found, switch to qN;
    - seek for letter 'c' to change it to 'x' too - if not found, switch to qN;
    - when no more 'a's found, seek for any 'b' or 'c' - if anything found, switch to qN - otherwise switch to qY.

    Word should be bordered by spaces, for example, so that machine could recognize the ends.

    on the first tape I have the representation of n ( 111111...11 - n+1 times), on the second tape I have 111 = representation of 2, and then on an additional tape
    It sounds you are trying to make matters more complicated than necessary. Store the values in binary system.

    Let the first tape to store the N, for example '11001', and the second tape at beginning should have only '0'.

    You need to write the procedure of decrement-by-one for the first tape:
    - seeking from the end, find first '1' and change it to '0';
    - then change all chars from this point to end to '1'.

    Now simply improve this procedure - let it add another '1' at the end of the number on the second tape - so you'll have successive values of '2^k-1'. (i.e. 01, 011, 0111, 01111 etc.)

    Stop when the value on the first tape have no more '1's
    CodeAbbey - programming problems for novice coders
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    3
    Rep Power
    0

    hi


    hi,

    okay

IMN logo majestic logo threadwatch logo seochat tools logo