28 Jun 2004 20:06:01 -0400

Related articles |
---|

Collatz Sequence Recognition quinn-j@shaw.ca (Quinn Tyler Jackson) (2004-06-14) |

Re: Collatz Sequence Recognition cdc@maxnet.co.nz (Carl Cerecke) (2004-06-21) |

Re: Collatz Sequence Recognition cdc@maxnet.co.nz (Carl Cerecke) (2004-06-28) |

From: | Carl Cerecke <cdc@maxnet.co.nz> |

Newsgroups: | comp.compilers |

Date: | 28 Jun 2004 20:06:01 -0400 |

Organization: | TelstraClear |

References: | 04-06-060 |

Keywords: | parse, theory |

Posted-Date: | 28 Jun 2004 20:06:01 EDT |

Quinn Tyler Jackson wrote:

*> Let L = {a^x b^y c^z | (x is odd in N, y = 3x+1, z = y/2) OR (x is even in*

*> N, y = x/2, z = (y is odd) ? 3y+1 : y/2}*

*>*

*> In other words -- let (x, y, z) be some 3-tuple s.t. they are a subset of*

*> some Collatz Sequence. Examples:*

*>*

*> aaaabbc (4, 2, 1)*

*> aaabbbbbbbbbbccccc (3, 10, 5)*

*> abbbbcc (1, 4, 2)*

*>*

*> Now, assume that rather than a, b, c, we rework it s.t. L_2 = {w_1^x_1*

*> w_2^x_2 ... w_n^x_n | n > 2, sigma = {1,0} s.t. letters of w_i and*

*> w_i+1 mod 2, and x_1 ... x_n are a Collatz sequence}, i.e.:*

*>*

*> 1111001 (4,2,1)*

*> 1110000001111111111000001111111111111111000000001111001 (3,10,5,16,8,4,2,1)*

^^^

111

The sequence should start with 111111, not 111000, and is (6,3,10,...)

*> 1. Would anyone here care to formally prove that L/L2 is/are [a] Type 1*

*> language(s), as opposed to Type 0?*

Both are type 1. That is, both can be recognised by a linear-bounded

non-deterministic Turing machine. Using the vtm2 software from

http://www.nmt.edu/~prcm/turing/, the following (linear-bounded) Turing

machine halts in the state IS_COLLATZ_TRIPLE if the sentence is in L,

and some other state if the sentence is not in L.

Save the TM to the file collatz.vtm and, for the input "abbbbcc", run

the TM using:

../vtm collatz.vtm -t_abbbbcc_ -b_ -seven_x -S -F

-TM code begins after this line-

# x = |a|

# y = |b|

# z = |c|

# state names could have been chosen better...

# decide whether x is odd

even_x,a,odd_x,a,R

odd_x,a,even_x,a,R

# x is odd, y = 3x + 1

# count b's by converting them to B. do the "+ 1" now

odd_x,b,find_a,B,L

# find the left-most a

find_a,a,find_a,a,L

find_a,_,found_a,_,R

find_a,A,found_a,A,R

found_a,a,find_b,A,R

find_b,a,find_b,a,R

find_b,B,find_b,B,R

find_b,b,find_b2,B,R

find_b2,b,find_b3,B,R

find_b3,b,skip_B_L,B,L

skip_B_L,B,skip_B_L,B,L

skip_B_L,a,find_a,a,L

skip_B_L,A,skip_B_R,A,R

skip_B_R,B,skip_B_R,B,R

# now, find y/2 c's. That is, one c for two B's

skip_B_R,c,two_b,C,L

two_b,C,two_b,C,L

two_b,B,two_b,B,L

two_b,A,change_B1,A,R

two_b,D,change_B1,D,R

change_B1,B,change_B2,D,R

change_B2,B,skip_to_c,D,R

skip_to_c,B,skip_to_c,B,R

skip_to_c,C,skip_to_c,C,R

skip_to_c,c,two_b,C,L

skip_to_c,_,no_B,_,L # check no B's left

no_B,C,no_B,C,L

no_B,D,IS_COLLATZ_TRIPLE,D,L # is a collatz triplet. y is even. z = y/2

# x is even, y = x/2

even_x,b,two_a,B,L

two_a,B,two_a,B,L

two_a,a,two_a,a,L

two_a,_,change_a1,_,R

two_a,A,change_a1,A,R

change_a1,a,change_a2,A,R

change_a2,a,skip_to_b,A,R

skip_to_b,a,skip_to_b,a,R

skip_to_b,B,skip_to_b,B,R

skip_to_b,b,two_a,B,L

skip_to_b,c,even_b,c,L # got |b| half of |a|, now count the b's

# count the b's

even_b,B,odd_b,B,L

odd_b,B,even_b,B,L

# even number of b's

even_b,A,skip_Beven,A,R

skip_Beven,B,skip_Beven,B,R

skip_Beven,c,two_b,C,L # now, find y/2 c's using code above.

# odd number of b's, z = 3x+1

odd_b,A,change_to_E,A,R

change_to_E,B,skip_to_c2,E,R

skip_to_c2,B,skip_to_c2,B,R

skip_to_c2,C,skip_to_c2,C,R

skip_to_c2,c,change_c2,C,R

change_c2,c,change_c3,C,R

change_c3,c,next_b,C,L

next_b,C,next_b,C,L

next_b,B,next_b,B,L

next_b,E,change_to_E,E,R

change_to_E,C,find_1_c,C,R # run out of B's, find one remaining c at end

find_1_c,C,find_1_c,C,R

find_1_c,c,am_i_blank,C,R

am_i_blank,_,IS_COLLATZ_TRIPLE,_,L

-TM code ends at previous line-

Recognising a Collatz sequence is Type 1, because we never need extra

tape to count how many of a particular symbol we have, in order to find

out how many of the next type of symbol we expect.

Changing the Turing machine spec to recognise L2 should not be too

difficult. (Exercise for the reader!)

*> 2. Would a grammar for such a language be "interesting"?*

I could only come up with an unrestricted grammar by hand, but a CSG can

be mechanically generated from a linear-bounded TM, such as the one

above (see Hopcroft and Ullman). As for "interesting"? Well, I'd rather

have the TM than the CSG. CSG's hurt my brain.

Cheers,

Carl.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.