I Explaining Enumerable: Understanding the Concept in Godel, Escher, Bach

[opus]

I'm reading a book called Godel, Escher, Bach, and the author is talking about formal systems, in particular, primes and composite numbers. He goes on to mention that "There exist recursively enumerable sets which are not recursive".
I don't understand the term "enumerable" though. The definition I found was "able to be counted by one-to-one correspondence with the set of all positive integers." But I don't get this either. Does it mean you can just count something consecutively?
To give context, the author is posing the question on whether or not there is a way to define prime numbers independently, without the use of composite numbers (I think).

 

[fresh_42]

I'm reading a book called Godel, Escher, Bach, and the author is talking about formal systems, in particular, primes and composite numbers. He goes on to mention that "There exist recursively enumerable sets which are not recursive".
I don't understand the term "enumerable" though. The definition I found was "able to be counted by one-to-one correspondence with the set of all positive integers." But I don't get this either. Does it mean you can just count something consecutively?
To give context, the author is posing the question on whether or not there is a way to define prime numbers independently, without the use of composite numbers (I think).

You can find the formal definitions on Wikipedia and the links there:
Chomsky type-0 grammar = recursively enumerable = recognizable by a TM = there exists a TM which will enumerate all valid strings of the language

Chomsky 1 (context sensitive) $\subsetneq$ recursive $\subsetneq$ Chomsky 0 (unrestricted)

 

[opus]

Oh man. I read all that and the wiki but I don't even know what to ask. Thats all way above my pay grade. I am in PreCalc so my Math knowledge is bare right now. That seems to be a little too deep for my experience level right now. Is therr a way to define enumerable without all that?

 

[fresh_42]

Oh man. I read all that and the wiki but I don't even know what to ask. Thats all way above my pay grade. I am in PreCalc so my Math knowledge is bare right now. That seems to be a little too deep for my experience level right now. Is therr a way to define enumerable without all that?

That's why I upgraded the thread to "I"ntermediate, because a correct answer requires a few technical terms as a language (math.) and a Turing machine.

Let me try to make it easy. A language is simply a collection of words given some alphabet and a grammar. E.g. our language here is English with a Latin alphabet. I'm not sure in which Chomsky category English falls, but it has certainly rules and is context sensitive. So I assume it is of a higher type than those we consider here. But as an example disregarding grammar rules, it will do. The term "set" in your post and in our context actually refers to those set of words, i.e. the language, and recursive and enumerable refer to the type of grammar. You've asked what recursive enumerable means, which means a language with unrestricted grammar, which basically means all combinations of words are allowed. In this language: "all allowed are English in language this words" is a correct sentence. No rules except that the words must be English. The dream of all schoolkids around the world.

The enumerability comes into account, if we formally want to gather all words of the language, i.e. write a lexicon. The Turing machine is a very basic idea of a computer. It can read and overwrite on an endless one dimensional storage tape, symbol by symbol. It is a model, not an actual computer. Now recursive enumerable means, that this machine can go back and forth on this tape, and whenever a valid word is found, it gives it a number to count it. It is quasi the author of our lexicon. Now the property recursive enumerable = Chomsky type 0 means, that this machine can find and eumerate all valid words, i.e. the entire lexicon. It says nothing about whether the machine will ever stop, or how long it takes, just that it is basically possible. It doesn't even make its lexicon readable, as there is no order to find words. They are just all included and enumerated.

 

[Erland]

To put it simple in this case:

A set S of natural numbers is recursively enumerable if there is an algorithm which produces natural numbers as output, one after an other, such that every number in S is eventually produced as output, but no numbers not in S are.

A set S of natural numbers is recursive if there is an algorithm which takes a natural number as input, and outputs yes if the input number belongs to S and outputs no otherwise (or something equivalent to yes/no).

"Algorithm" can be understood in terms of Turing machines, primitive recursive and recursive functions, Lambda Calculus, Hofstadter's programming languages BlooP and FlooP, and many other equivalent characterizations.

 

[mfb]

Here is an example for a set that is recursively enumerable but not recursive.

 

[opus]

Thanks for the helpful responses everyone. I think I'm starting to get the general idea! I will keep poking it and come back if I have any questions. Thank you very much!