CODEWITHSUNDEEP
turing-machinescomputation
Tim T
Tim T

Reputation: 333

Turing machine: such that for every word w in {a,b}*, it will change every a to b and b to a, and then halt

I need to describe formally (by means of transition function) a Turing Machine such that every word w in {a,b}* , it will change every a to b, and every b to a.

I have had a go, and this is my solution:

(s,a) -> (s,b,R)

(s,b) -> (s,a,R)

(s,blank) -> (n,blank)

where n is the halting state and s is the starting state

Does this work? Thanks!

Upvotes: 1

Views: 913

Answers (3)

trincot
trincot

Reputation: 351218

Yes, it works. You can test your transition table here:

createTuring({
    transitions: [
        { state: "s", read: "a", nextState: "s", write: "b", move: "R" },
        { state: "s", read: "b", nextState: "s", write: "a", move: "R" },
        { state: "s", read: "_", nextState: "n", write: "_" },
    ],
    initState: "s",
    tape: "aabbabbaba",        
})
<script src="https://trincot.github.io/turing.js"></script>

We can see that at a given position of the tape, if it has an "a" or a "b", there is an applicable transition, and it will flip the character.

As the input only consists of "a" and "b", and the applicable transitions move the head to the right, the head will arrive at a blank after 𝑛 steps (and as many flips), where 𝑛 is the size of the input. This triggers the accept state, so that at the accept state all 𝑛 input characters have been flipped.

Upvotes: 0

Patrick87
Patrick87

Reputation: 28322

Your TM works correctly. If you are comfortable with the notation of TMs it's almost obvious that yours works, so formal proof seems like overkill, but if you really insist a proof by mathematical induction on the length of the input is straightforward.

Claim: the TM given performs the function described.

Proof: the proof is by strong mathematical induction on the length m of the input string initially recorded on the TM's tape.

Base case: if the input tape contains the empty string then the TM executes transition (s,blank) -> (n,blank) and therefore halts without changing any tape symbols. Because the resulting string left on the tape is unchanged, it is the empty string. It is vacuously true that the empty string is equivalent to the empty string after replacing all a's with b's and vice versa; there are no symbols in the string to contradict this.

Induction hypothesis: assume that the TM correctly processes all input strings of length up to and including k.

Induction step: we must show that the TM correctly processes all input strings of length equal to k + 1. Note that any input string of length k + 1 over the alphabet {a, b} is equal to some input string of length k, with either the symbol a or the symbol b appended to it. We have already found that the TM processed strings of length k correctly; that is, it flipped all a's to b's and vice versa. Furthermore, because the TM must have halted, the last transition it executed was (s,blank) -> (n,blank). If instead of having seen blank on the tape at this point, it had instead seen a or b, we would be in the present case: that is, the TM would have made it to the same position by processing the prefix of length k of our string of length k + 1. Instead of executing the transition (s,blank) -> (n,blank) it would be forced to execute one of the transitions (s,a) -> (s,b,R) or (s,b) -> (s,a,R), depending on whether the (k + 1)th symbol is a or b. These transitions will correctly flip the symbol at position k + 1, leaving a string of k + 1 where all symbols were correctly exchanged. The next transition will see blank and transition to the halting state. This concludes the proof.

Upvotes: 0

BitTickler
BitTickler

Reputation: 11947

The usual approach to questions of this kind is either "test" or "proof". Here, I show how you can easily test if your approach succeeds:

GHCi, version 8.2.2: http://www.haskell.org/ghc/  
:? for help
Prelude> :{
Prelude| cnv ('a':xs) = 'b':cnv xs
Prelude| cnv ('b':xs) = 'a':cnv xs
Prelude| cnv [] = []
Prelude| :}
Prelude> cnv "abaaab"
"babbba"
Prelude>

At least in my eyes, this haskell code looks similar enough to your transition specification. The [] case in the third line of the definition of the cnv function stands for "empty list", i.e. it is your halting state. And for the recursion of this function it is the base case where recursion stops.

As for how to formally proof if your automata ends, I am not enough of a computer science guy to help you with that. Someone else might.

Upvotes: 1

Related Questions