# Collatz Sequence Recognition

## Quinn Tyler Jackson <quinn-j@shaw.ca>14 Jun 2004 17:45:06 -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: Quinn Tyler Jackson Newsgroups: comp.compilers Date: 14 Jun 2004 17:45:06 -0400 Organization: Compilers Central Keywords: parse, theory, question Posted-Date: 14 Jun 2004 17:45:06 EDT

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)
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

Post a followup to this message