Help with turing machines

d1.psy

New member
Joined
Nov 28, 2015
Messages
9
I need to write 2 turing machine programs.
1. This programm must compute this function: f(x,y) = x + 2y
2. A random word is written on a tape (it can be empty) in alphabet A = {a,b,c} (next symbols on the tape are empty). Programm must replace every 2nd letter in the word with a. Example: bbcabc -> bacaba. Head looks at first letter of the word.
Please, help me(
 
Last edited:
I need to write 2 turing machine programs.
1. This programm must compute this function: f(x,y) = x + 2y
2. A random word is written on a tape (it can be empty) in alphabet A = {a,b,c} (next symbols on the tape are empty). Programm must replace every 2nd letter in the word with a. Example: bbcabc -> bacaba. Head looks at first letter of the word.
Please, help me(

What are your thoughts? What have you done so far? Please show us your work even if you feel that it is wrong so we may try to help you. You might also read
http://www.freemathhelp.com/forum/threads/78006-Read-Before-Posting
 
What are your thoughts? What have you done so far? Please show us your work even if you feel that it is wrong so we may try to help you. You might also read
http://www.freemathhelp.com/forum/threads/78006-Read-Before-Posting
attachment.php

This is a code for the first function I've made so far. It's not working. About 2nd function - I just have no idea what to do. I've been sitting on it for a few hours already. "Turing machines" is a new topic in my "Algorith theory" subject in university, and I just can't understand it.
 

Attachments

  • 8M0ogmwD9w0.jpg
    8M0ogmwD9w0.jpg
    4.5 KB · Views: 19
  • EUi2RNmsFhY.jpg
    EUi2RNmsFhY.jpg
    5.1 KB · Views: 34
What are your thoughts? What have you done so far? Please show us your work even if you feel that it is wrong so we may try to help you. You might also read
http://www.freemathhelp.com/forum/threads/78006-Read-Before-Posting
attachment.php

This is a program I've made so far for my 1st function. But it's not right. 2nd function... I've tried to understand for a few hours, how to do it. No result. It's a new topic in Algorithm theory in my university, so I don't understand it quite well yet. And I found this specific topic to be the hardest one yet for me to understand. That's why I came here for help
 

Attachments

  • EUi2RNmsFhY.jpg
    EUi2RNmsFhY.jpg
    5.1 KB · Views: 36
Last edited:
attachment.php

This is a program I've made so far for my 1st function. But it's not right. 2nd function... I've tried to understand for a few hours, how to do it. No result. It's a new topic in Algorithm theory in my university, so I don't understand it quite well yet. And I found this specific topic to be the hardest one yet for me to understand. That's why I came here for help

The row numbers appear to be the instruction states and the column numbers appear to be the symbols. Thus, in state 1 (row labeled 1), if the head
(a) reads the symbol 1, it writes a 1, moves the tape (head?) left and transitions to state 2
(b) reads the symbol 2, it writes a 1, moves the tape (head?) left and stays in state 1.
If this is not the case, would you please clarify?

Also, three questions and an observation: What is the initial value on the tape? Where is the head initially placed? Does the tape or the head move (generally it is the tape but some have used the head)? Also, there should likely be more than two symbols depending on just what base you are using for your numbers.

BTW, a nice notation I've seen is demonstrated at
http://aturingmachine.com/examplesSyntax.php
which is
( State Number, Symbol Read) -> ( Next State Number, Symbol To Write) Next Cell
Thus, for a stationary head,
(1,0) -> (1,1) Left
means "For state 1, if I read a zero, then write a one, remain in state 1 and move the tape right" and
(1,B) -> (B,1) Halt
means "For state 1, if I read a blank, then write a blank, remain in state 1 and stop the program.
 
The row numbers appear to be the instruction states and the column numbers appear to be the symbols. Thus, in state 1 (row labeled 1), if the head
(a) reads the symbol 1, it writes a 1, moves the tape (head?) left and transitions to state 2
(b) reads the symbol 2, it writes a 1, moves the tape (head?) left and stays in state 1.
If this is not the case, would you please clarify?

Also, three questions and an observation: What is the initial value on the tape? Where is the head initially placed? Does the tape or the head move (generally it is the tape but some have used the head)? Also, there should likely be more than two symbols depending on just what base you are using for your numbers.

BTW, a nice notation I've seen is demonstrated at
http://aturingmachine.com/examplesSyntax.php
which is
( State Number, Symbol Read) -> ( Next State Number, Symbol To Write) Next Cell
Thus, for a stationary head,
(1,0) -> (1,1) Left
means "For state 1, if I read a zero, then write a one, remain in state 1 and move the tape right" and
(1,B) -> (B,1) Halt
means "For state 1, if I read a blank, then write a blank, remain in state 1 and stop the program.
I've told you everything that's known. Initial value, position is not known in 1st program.
 
I think I understand it better now. And sorry, I've made a mistake with the previous image. I'm sure the head supposed to be located here
attachment.php

and this is my new code
 

Attachments

  • bcNgBXba4qY.jpg
    bcNgBXba4qY.jpg
    9.7 KB · Views: 9
Yes! I've managed to do 2nd program. It's working. But I'm still stuck with my first program
attachment.php
 

Attachments

  • ZQpBXXpNCT0.jpg
    ZQpBXXpNCT0.jpg
    9.7 KB · Views: 9
Yes! I've understood! I did all of them.
attachment.php
 

Attachments

  • 4OBDe2cF2f8.jpg
    4OBDe2cF2f8.jpg
    15.9 KB · Views: 8
Puzzle Turing machine

We are activly working on a turing machine code that can make a pyramid out of nothing ( from --------------------- to -----7654321234567---). Our restrictions are that we have 7 states to do the coding, we need to make a pyramid that is as big as possible and must end. The alphabet we can use is: the numbers for the pyramid that are necessary for the pyramid; ''-''; ''X'' . Let see some of you smart people can beat us ;) (we have been able to reach a pyramid of 7)
 
Top