ontolog-forum
[Top] [All Lists]

Re: [ontolog-forum] HOL decidability

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: "doug foxvog" <doug@xxxxxxxxxx>
Date: Wed, 13 Oct 2010 10:43:40 -0400 (EDT)
Message-id: <56256.71.178.11.66.1286981020.squirrel@xxxxxxxxxxxxxx>
On Tue, October 12, 2010 23:18, Rich Cooper said:
> Christopher Menzel wrote:
>> On 12/10/2010 6:48 PM, Rich Cooper wrote:
> ...
>>> I'm sure you remember that the set of primes is
>>> infinite, and that there is no (known) function that can iterate them.    (01)

>> Of course there is.  For any given number n>1, it is easy to test
>> whether n is prime.  For a particularly crude algorithm, for each i<n
>> (i>1), look for a number j<n (j>1) such that ij=n.  If you fail to find
>> such an i, then n is prime.
>>  To construct a list of the primes, apply the above
>> procedure to each number in turn, starting with 2, adding the primes you
>> discover to the list as you go.  This informal procedure is easily
>> expressed
>> formally as a recursive function; one typically demonstrates this in the
>> first week or two of a course on computability.    (02)

> RC: I didn’t say there was no way to calculate them; I said there is no
> function that iterates them.  And your algorithm above iterates integers
> till it starts to factor, then continues to factor forever without
> returning if the number is unfactorable (i.e., if its prime).
> Your program does not iterate primes.    (03)

This does not factor forever as the loop that tests factorization loops
on integers such that (i>1 and i<n).  The second integer of the
factorization is also limited to (j>1 and j<n).  Thus the loop is finite
and does not go on forever.    (04)

>...    (05)

-- doug foxvog    (06)

=============================================================
doug foxvog    doug@xxxxxxxxxx   http://ProgressiveAustin.org    (07)

"I speak as an American to the leaders of my own nation. The great
initiative in this war is ours. The initiative to stop it must be ours."
    - Dr. Martin Luther King Jr.
=============================================================    (08)


_________________________________________________________________
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    (09)

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