Re: Collatz Sequence Recognition

Carl Cerecke <cdc@maxnet.co.nz>28 Jun 2004 20:06:01 -0400

From comp.compilers

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)
| List of all articles for this month |

 From: Carl Cerecke 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

> 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

> 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