Help with turing machines

[d1.psy]

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(

 

[Ishuda]

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

 

[d1.psy]

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

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.

 

[d1.psy]

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

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

 

[Ishuda]

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.

 

[d1.psy]

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.

 

[Ishuda]

I've told you everything that's known. Initial value, position is not known in 1st program.

You need to know more about Turing Machines through review of your class notes and texts. A fairly nice write up is also available at
http://web.stanford.edu/class/archive/cs/cs103/cs103.1134/lectures/17/Small17.pdf

 

[d1.psy]

You need to know more about Turing Machines through review of your class notes and texts. A fairly nice write up is also available at
http://web.stanford.edu/class/archive/cs/cs103/cs103.1134/lectures/17/Small17.pdf

Thanks for the help, but I'm afraid it didn't help me. I still can't understand how to build functions like that I mine.

 

[d1.psy]

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

and this is my new code

 

[d1.psy]

Yes! I've managed to do 2nd program. It's working. But I'm still stuck with my first program

 

[d1.psy]

Yes! I've understood! I did all of them.

 

[Backfishbone]

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)