Groupings.

[TuringAI]

I imagine that everyone here has heard of set theory. Well I've conceived of another kind of set-like object and I can explain it but I don't know what it's called, so I will call it groupings.

A grouping is related to sets in a number of ways, but they differ in that with sets you can't have two of the same element, but with groupings you can, and with sets the order doesn't matter, but with groupings it does. Also true is that with sets you can have any number of elements, but with groupings while there is no finite limit they can't be infinite. This next point is perhaps the essential point: With sets you don't know what is going to be in the set, whereas with groupings you know it can be either another grouping or a blank character.

If you don't understand, I will show you. A set is like {1,2,{4,9},12,...}. A grouping is like {,{},{,,},{}}.

Now I have this nice way of representing groupings as a number in binary. Any blank character is represented as a 0. Any set is represented by a 0 and then a number of 1s depending on how many elements (blank characters or groupings) there are. For example, a grouping with one blank character is 001, a grouping with two blank characters is 00011, and so on. Now, finally, once we have the outermost grouping you add a 1 at the end to indicate that it is not inside anything else. So let's say you have a grouping as such: {,,{}}. You would represent it in binary as 0000101111. Now it's quite obvious that the blank character can be taken as a grouping with no elements, so let's call it the empty grouping. Then groupings only contain other groupings, whether this grouping is empty or non-empty. Also notice how that which is in a grouping is always to the left of that grouping.

The thing I discovered is not only can any grouping with finite recursion be represented in binary, but the only rule that has to be obeyed for the binary representation to be proper is that the number of 0s match up with the number of 1s. I will explain why this is so if anybody wants to hear the reason.

Addendum: Another thing is that any grouping must start with a 0 and end with a 1; and in between, reading from left to right, the 1s must be exhausted before the 0s are exhausted. I forgot to mention that. Ooops.

PS: I know that the language is ambiguous, but bear with me. Let me at least clarify now that any WHOLE groupings must have the same number of 0s and 1s whereas any PARTIAL groupings won't, and in fact they'll be different in the number of 0s and 1s, where the 0s will outnumber the 1s by a single digit.

Edited December 3, 2008 by TuringAI

[TuringAI]

Okay, now I am in the process of trying to see if there is a way to make a multiple-state two-symbol Turing Machine that will be able to do any kind of meaningful operations on the groupings (which, in retrospect, should have been called something else) which does not destroy any information. Wish me luck!

[TuringAI]

Okay, now I am in the process of trying to see if there is a way to make a multiple-state two-symbol Turing Machine that will be able to do any kind of meaningful operations on the groupings (which, in retrospect, should have been called something else) which does not destroy any information. Wish me luck!

I've decided to call these 'groupings' referent chain lists, or RCLs, for short.

I've figured out (but with no 'proof') that to make a turing machine work with the data you have to have the data entered correctly and the pointer has to be on the very last 1 instead of the very first 0. There's no way to tell if it hasn't been entered correctly so it is just assumed. Either it goes too far to the left and jams, or it doesn't go far enough to the left and it misses some digits. Now I've downloaded a turing machine program, probably not the best one, but the only one available, and I'm going to try to see if I can at the very least count how many 1s and 0s there are.

[John Link]

It is not clear to me exactly what a grouping is, and with the description you've given I don't see why you would be interested in such a concept. Please explain more clearly what a grouping is, providing several examples (as well as a definition, if you are able to formulate one), and explain how you think the concept of grouping is useful.

Edited December 8, 2008 by John Link

[TuringAI]

It is not clear to me exactly what a grouping is, and with the description you've given I don't see why you would be interested in such a concept. Please explain more clearly what a grouping is, providing several examples (as well as a definition, if you are able to formulate one), and explain how you think the concept of grouping is useful.

A grouping is an n-member list, where each member is also an n-member list, where any particular n can be 0 and where the total number of lists is finite. That would be a fairly decent definition.

Given this definition, each 'grouping' can, for instance, be represented as a series of 0s and 1s whereupon the number of 0s and 1s is equal. It can also be represented like a tree. It can also be represented with "(" ")" "_" and ","as symbols. You can also represent it in words. My preferred method is 0s and 1s.

A null list, a list of no lists, would be represented as 01. The 0 means the list is empty and the 1 following it means that the sequence terminates.

A list of the null list would be represented as 0011. The 01 is the list OF some list, and the 0 is the list that serves as its sole element.

A list of two null lists would be represented as 000111. A list of a list of the null list would be represented as 001011.

You can see why I have a 1 at the end. It's a contextual indicator so that you know when the list isn't itself considered an element of another list.

I'm not sure what purpose this abstraction serves except as an abstraction, so that tree structures can be put into 0s and 1s for the purpose of being used by a Turing Machine. As with most math these days, people will find a use after it's already been studied enough for it to be understood.

[Ordr]

I imagine that everyone here has heard of set theory.

Not only have I never heard of it, but the complexity of the explanation that you've given terrifies me.

[TuringAI]

Not only have I never heard of it, but the complexity of the explanation that you've given terrifies me.

It's easier to imagine visually. It's basically a tree with a finite number of nodes, or a finite series of line segments or a point, depending on how trivial you want to be. For example 00100100101111 is a tree which has a point at the beginning, branches off into three, and each of the three branches just continues linearly for a whole segment, but no more. So there is one beginning node and three end nodes, and three middle nodes.

If you'd like I could draw a picture.

[John Link]

A grouping is an n-member list, where each member is also an n-member list, where any particular n can be 0 and where the total number of lists is finite. That would be a fairly decent definition.

Well, it's a start, but not yet clear. I see that you are using a recursive definition ("A grouping is an n-member list, where each member is also an n-member list"). I think your definition could be rephrased as follows: "A grouping is a finite list of finite lists." I don't know that the rephrasing is any better; I'm just trying to understand what you have in mind, which is not so easy since you haven't given any examples! Please provide several (not just one or two) examples of groupings. Then we'll know what you're talking about.

Also, you haven't explained what you mean by a list. Whether or not you can formulate a definition, please give some examples.

I'm not sure what purpose this abstraction serves except as an abstraction, so that tree structures can be put into 0s and 1s for the purpose of being used by a Turing Machine.

You started this thread with an assumption that your readers were familiar with set theory, but now you seem to assume that we also know about tree structures and Turing machines. That does not help anyone understand what you are writing about.

As with most math these days, people will find a use after it's already been studied enough for it to be understood.

But why and how did you come up this this concept?

Edited December 8, 2008 by John Link

[John Link]

Not only have I never heard of it, but the complexity of the explanation that you've given terrifies me.

Don't worry, basic set theory is fundamentally simple. Anyway, what TouringAI has written is NOT an explanation of set theory.

[TuringAI]

Well, it's a start, but not yet clear. I see that you are using a recursive definition ("A grouping is an n-member list, where each member is also an n-member list"). I think your definition could be rephrased as follows: "A grouping is a finite list of finite lists." I don't know that the rephrasing is any better; I'm just trying to understand what you have in mind, which is not so easy since you haven't given any examples! Please provide several (not just one or two) examples of groupings. Then we'll know what you're talking about.

Also, you haven't explained what you mean by a list. Whether or not you can formulate a definition, please give some examples.

You started this thread with an assumption that your readers were familiar with set theory, but now you seem to assume that we also know about tree structures and Turing machines. That does not help anyone understand what you are writing about.

But why and how did you come up this this concept?

Well I apologize for not being clear. I will start with the simple question. I came up with this concept because I wanted to know if I could come up with a way to represent sets in binary. Then I realized that sets were too general in some aspects and too specific in other aspects, so I created groupings, a type of lists. I don't think I want to call them groupings though... too similar to groups.

I am trying right now to give a definition of my list in terms that people not as familiar with mathematics can understand. For starters, there were the four given. I can re-explain those if so desired.

01 is a binary representation of a grouping. The grouping here is the empty list. It exists but does not refer to anything, and in this context it is not something to which some other thing refers. The 0 represents that it's empty, and the 1 represents its completion since nothing refers to it.

0011 is another one, but a tad more complex. The 01 there in the middle isn't the same as above. Instead, it's saying "There is a list with one element". The 0 to its left is the list of zero elements to which it refers. The 1 to its right is, again, its completion.

000111 is a list of two empty lists. The 011 means "There is a list of two elements". You can tell because, aside from the last 1, there are two 1s next to that zero. The two zeroes to the left are the elements, empty lists. And again, the 1 on the right is to avoid confusion.

001011 is a list of a list of an empty list. Instead of the first 01 referring to a 0, it refers to another 01 which itself refers to a 0. The 1 serves the obvious purpose here as it did before.

Two things I should explain. One is that there is a zero next to the 1s that separates the list and its elements. The reason for that should be obvious, as otherwise we'd be confused by something as simple as 0011. Does that 1 on the right refer to the 001, or is it part of the 11? A similar thing is noted about the 1 at the end. This is simply there because reading it left to right, we need to know where the sequence terminates. Also, even right to left it's needed as a default digit that assures us that we're starting in the right place.

Currently I cannot reference any concretes that this represents. It is a higher level abstraction that can possibly have some use in representing any tree like structure. In fact, that there is a binary representation of a treelike structure is the point. A treelike structure would be like evolutionary paths, or other kinds of decision trees.

[Guest ArenaMan]

A grouping is related to sets in a number of ways, but they differ in that with sets you can't have two of the same element, but with groupings you can, and with sets the order doesn't matter, but with groupings it does. Also true is that with sets you can have any number of elements, but with groupings while there is no finite limit they can't be infinite. This next point is perhaps the essential point: With sets you don't know what is going to be in the set, whereas with groupings you know it can be either another grouping or a blank character.

If you don't understand, I will show you. A set is like {1,2,{4,9},12,...}. A grouping is like {,{},{,,},{}}.

Is this concept any different than having lists with a single element? I think {,{},{,,},{}} would be better written as (b,(),(b,b,\,(\), where I've used b for "blank" (i've had to use \b so it didn't do this ). A better definition might be something like

A grouping is a tuple that is either empty, or non-empty, in which case its elements can be one of the following types:

(i) Another grouping

(ii) A blank element

By the way, there is a way to represent binary trees as binary strings with certain properties. I can't find my notes from my combinatorics class, but it has to do with how the number of binary trees with 2n+1 nodes is the same as the number of those types of binary strings of length n... or something like that (counted by the nth Catalan number).

By the way, anything you can encode on a computer can be represented in binary, of which sets are included.

Edited February 28, 2009 by ArenaMan