From a circuit to a Turing machine [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

I have read my book everything that says about turing machines and how they work but i havent got a single clue of how to make this essay.Even though i managed to get all exersices right about Turing machines this just makes me hit my head up in the wall.so here is goes

http://postimg.org/image/ja4o7c28f/

(hope this works!)

Thats the circuit i need to build it to turing machine that gets the A,B,C with true or false prices.

First, I don't understand how to read the diagram. I am trying to understand what happens after each signal goes through the -|>o- (not) thingy - I know that they will be the opposite of what they where, but if A goes through it it will come as A' - then what happens when it gets into line with the other A'?

Even when I have that figured, I'm struggling with how to express this as a Turing Machine.

Sorry for my bad use of english but as being in the first semester to make it easy for everyone in my university they use translated programming into Greek and i dont yet know the right words to explain my problem in programming !

Thank you in advance for even making a try to read all this :)

Answer 1

I don't really understand your question. You said "So if A goes through it it will come as A' but what happens when it gets into line with the other A'?. So far, this is the only question you asked.

The answer to this question is that in the diagram you are looking at, there are only "connections" at the end of lines. So where A crosses over A', there is no connection, no interaction.

The output function of the diagram you posted is:

Out = A'BC + AB'C + ABC'

IE the output is true if any only if only one of the inputs is false.

So that was part 1 of what you were asking.

To represent this as a Turing machine, you need to decide what "states" you have. It seems clear that what matters is "which input have I seen before being false?". This means that you need states that tell you which of the inputs have been seen being false. The possible combinations are:

1. I've seen no false inputs yet
2. I've seen A' only
3. I've seen B' only
4. I've seen C' only

From each of these states, you will get to one of the others, or the final answer.

The rule for state 1 will be "if the input is false, then move to the appropriate state (2,3, or 4) and move the tape right.

The rule for each of the other 3 states will be "if the input is false, and it's not the one I've already seen, then reject. If the input is not false, then just move the tape right.

If you need reach the "accept" state, or halt after you've processed three inputs, then you need a few more states so you can keep track of how many you've seen already.

Answer 2

So here is the file :) i had to to go through 8 values

000
001
...
111

and from the circuit i can see as you told me Jade that only if i got 2 true values and only then i would have true as a final value so here is goes in turing machine

4η Άσκηση

>      
>     Start         *           *        Right      Kat
>     Kat           1           1        Right      S1
>     Kat           0           0        Right          L1
>     Kat           *           *        None           False
>     S1            1           1            Right      S2
>     S1            0           0        Right      S1  
>     S1            *           *        None           False
>     L1            1           1        Right      S1
>     L1            0           0        Right      L2
>     L1            *           *        None       False
>     S2            1           1        Right      False
>     S2            0           0        Right      True
>     S2            *           *        None       True
>     L2            1           1        Right      False
>     L2            0           0        Right      False
>     L2            *           *        None       False
>     False         1           1        None       End
>     False         0           0        None       End
>     False         *           *        None       End
>     True          0           0        None       End
>     True          1           1        None       End
>     True          *           *        None       End