Compilers - Collatz Sequence Recognition

Author

Collatz Sequence Recognition

Quinn Tyler Jackson

2004-06-25, 7:45 pm

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)
1110000001111111111000001111111111111111
000000001111001 (3,10,5,16,8,4,2,1)
etc.

1. Would anyone here care to formally prove that L/L2 is/are [a] Type 1
language(s), as opposed to Type 0?
2. Would a grammar for such a language be "interesting"?

--
Quinn

Carl Cerecke

2004-06-28, 8:59 pm

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)
> 111000000111111111100000111111111111111
1000000001111001 (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.

Sponsored Links