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:

Ishuda

Elite Member
Joined
Jul 30, 2014
Messages
3,345
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

New member
Joined
Nov 28, 2015
Messages
9
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.
 

Attachments

d1.psy

New member
Joined
Nov 28, 2015
Messages
9
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
 

Attachments

Last edited:

Ishuda

Elite Member
Joined
Jul 30, 2014
Messages
3,345

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

New member
Joined
Nov 28, 2015
Messages
9
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

Elite Member
Joined
Jul 30, 2014
Messages
3,345

d1.psy

New member
Joined
Nov 28, 2015
Messages
9

d1.psy

New member
Joined
Nov 28, 2015
Messages
9
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
 

Attachments

d1.psy

New member
Joined
Nov 28, 2015
Messages
9
Yes! I've managed to do 2nd program. It's working. But I'm still stuck with my first program
 

Attachments

d1.psy

New member
Joined
Nov 28, 2015
Messages
9
Yes! I've understood! I did all of them.
 

Attachments

Backfishbone

New member
Joined
Feb 4, 2019
Messages
1
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