ontolog-forum
[Top] [All Lists]

Re: [ontolog-forum] HOL decidability [Was: using SKOS forcontrolled valu

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Ed Barkmeyer <edbark@xxxxxxxx>
Date: Wed, 13 Oct 2010 18:22:45 -0400
Message-id: <4CB63135.5080700@xxxxxxxx>
I shouldn't get into this, but...    (01)

Rich Cooper wrote:
> Thanks for the routine, but that is not an iterator of primes; it is 
> an iterator of integers.  By iterating through all the integers, your 
> routine finds primes, but it does not iterate the primes.  The fact 
> that you close the scope around tests for primes doesn’t make it an 
> iterator.  
>
>  
>
> The idea behind the iterator is to produce one new one, given the old 
> one as a starting point. 
>    (02)

That is one version of the inductive model of iteration.  The more 
robust version is to produce the next one, given all predecessors.  And 
of course, Bill's code does just that.  The "all predecessors" approach 
is equally valid mathematically, and it works for spaces with partial 
orderings, while the "from n, produce n+1" approach does not (in general).    (03)

Rich's model doesn't work for Fibonacci numbers, either, even though you 
only need two predecessors.     (04)

I suppose it would work for Cauchy enumeration of n-tuples, which is the 
common countability proof technique.    (05)

>
> The method you are using is often called Eratosthenes’ Sieve, which is 
> a well known method to calculate primes, but NOT to iterate them.  
>   The difference is in what is being enumerated inside the code. 
>    (06)

Well, more carefully, the Sieve of Eratosthenes is an iterative 
algorithm for producing all prime numbers.     (07)

I am familiar with the term "iterator" only as a software object, and 
OBTW, java.util.Iterator is class of somewhat diverse "objects" 
(algorithms), none of which takes an instance and produces the next.  
Instead, each has a retained state, and each invocation of next() 
produces the successor state and returns the corresponding instance of 
the "collection".  Thinking of prime numbers as an infinite collection, 
such an "iterator" will be seen to produce the primes in order starting 
from an initial state, while the actual implementation mechanism is 
"encapsulated" (and might well be the Sieve).  IMO, that is actually 
pretty close to the mathematical notion, in which the creature is 
categorized by a certain set of properties that it exhibits, regardless 
of what other bizarre properties it may have.  Which only means that a 
Java "iterator" is not a Rich Cooper "iterator".    (08)

So, as far as I can tell, Rich asserts that Bill's algorithm is not an 
instance of the definition Rich assigns to "iterator" above.  I agree.  
Now, how that relates to decidability, which is about the existence of 
an algorithm that terminates in finite time, I am at a loss to 
understand.   The ontolog forum exploder does seem to be a study in 
"free association."    (09)

-Ed    (010)

>  
>
> -Rich
>
>  
>
> Sincerely,
>
> Rich Cooper
>
> EnglishLogicKernel.com
>
> Rich AT EnglishLogicKernel DOT com
>
> 9 4 9 \ 5 2 5 - 5 7 1 2
>
> ------------------------------------------------------------------------
>
> *From:* ontolog-forum-bounces@xxxxxxxxxxxxxxxx 
> [mailto:ontolog-forum-bounces@xxxxxxxxxxxxxxxx] *On Behalf Of *Bill 
> Andersen
> *Sent:* Wednesday, October 13, 2010 12:52 PM
> *To:* [ontolog-forum] ; Rich Cooper
> *Subject:* Re: [ontolog-forum] HOL decidability [Was: using SKOS 
> forcontrolled values for controlledvocabulary]
>
>  
>
> On Oct 13, 2010, at 01:56 , Rich Cooper wrote:
>
>
>
> Hi Duane, yes, iterators in software were what I tried to convey 
> there.  There is no function that will iterate the primes.  By pairing 
> each prime in ascending order with any other iterated set, you create 
> unique prime keys for each element of that set, keys that cannot be 
> factored.  
>
>  
>
> Thanks for your inputs,
>
> -Rich
>
>  
>
> Hi Rich
>
>  
>
> Here's a fixed precision implementation of a prime iterator, along the 
> lines Chris Menzel described.
>
>  
>
> Enjoy
>
> ------------
>
>  
>
> package foo;
>
>  
>
> import java.util.Iterator;
>
>  
>
> public class PrimeIterator implements Iterator<Integer> {
>
>  
>
>        private Integer n = 2;
>
>       
>
>        @Override
>
>        public boolean hasNext() {
>
>               // Thanks to _Euclid_ :-D
>
>               return true;
>
>        }
>
>       
>
>        private boolean isPrime(Integer n) {
>
>               Integer i = 2;
>
>               while (i < n) {
>
>                      if ((n % i) == 0) {
>
>                            // _divisible_ by i < n
>
>                            return false;
>
>                      }
>
>                      i++;
>
>               }
>
>               return true;
>
>        }
>
>  
>
>        @Override
>
>        public Integer next() {
>
>               while (!isPrime(n)) {
>
>                      n++;
>
>               }
>
>               Integer tmp = n;
>
>               n++;
>
>               return tmp;
>
>        }
>
>  
>
>        @Override
>
>        public void remove() {
>
>               throw new UnsupportedOperationException();
>
>        }
>
>       
>
>        public static void main(String[] argz) {
>
>               PrimeIterator iter = new PrimeIterator();
>
>               while (iter.hasNext()) {
>
>                      System.out.println(iter.next());
>
>               }
>
>        }
>
>  
>
> }
>
>  
>
> Bill Andersen 
>
> Highfleet, Inc. (www.highfleet.com <http://www.highfleet.com>)
>
> 3600 O'Donnell Street, Suite 600
>
> Baltimore, MD 21224
>
> Office: +1.410.675.1201
>
> Cell: +1.443.858.6444
>
> Fax: +1.410.675.1204
>
>  
>
>  
>
>
>
>  
>    (011)

-- 
Edward J. Barkmeyer                        Email: edbark@xxxxxxxx
National Institute of Standards & Technology
Manufacturing Systems Integration Division
100 Bureau Drive, Stop 8263                Tel: +1 301-975-3528
Gaithersburg, MD 20899-8263                FAX: +1 301-975-4694    (012)

"The opinions expressed above do not reflect consensus of NIST, 
 and have not been reviewed by any Government authority."    (013)


_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (014)

<Prev in Thread] Current Thread [Next in Thread>