Re: Primitive Recursive Arithmetic

Article View: comp.lang.functional

Article #317

Back to comp.lang.functional Previous Next

#317

From: news
Date: Fri, 15 Jun 1990 19:11

17 lines
1287 bytes

In article <15591@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu
(victor yodaiken) writes:

   How about a function F_k: HCLWFF -> {T,F, TimedOut}
   where for horn clause wff P, F_k(P)= TimeOut if
   the algorithm does not conclude within j**j**j**j ...
					     k exponentiations
   steps, where j is the length of P and k is a parameter bounding
   the length. For decent sized k, 
   F_k(P) = TimedOut means that P is not feasibly decidable using this
   algorithm.

heh!

so I just make a set of cover functions for all the system calls that
plug in the largest representable numeric value for the termination
parameter.  What's been accomplished?

Technical Details

Message-ID: <10227@chaph.usc.edu>

Path: arc1-ca.pugleaf.net!utzoo!attcan!uunet!samsung!sdd.hp.com!zaphod.mps.ohio-state.edu!usc!chaph.usc.edu!usc.edu!news

References:

<15421@dime.cs.umass.edu> <GUTTMAN.90Jun12105623@darjeeling.mitre.org> <15548@dime.cs.umass.edu> <3594@rex.cs.tulane.edu> <15591@dime.cs.umass.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!attcan!uunet!samsung!sdd.hp.com!zaphod.mps.ohio-state.edu!usc!chaph.usc.edu!usc.edu!news
From: news@usc.edu
Newsgroups: comp.lang.functional
Subject: Re: Primitive Recursive Arithmetic
Message-ID: <10227@chaph.usc.edu>
Date: 15 Jun 90 19:11:49 GMT
References: <15421@dime.cs.umass.edu>
 <GUTTMAN.90Jun12105623@darjeeling.mitre.org> <15548@dime.cs.umass.edu>
 <3594@rex.cs.tulane.edu> <15591@dime.cs.umass.edu>
Sender: news@chaph.usc.edu
Organization: University of Southern California, Los Angeles, CA
Lines: 17
In-reply-to: yodaiken@freal.cs.umass.edu's message of 14 Jun 90 19:32:50 GMT

Reply to Parent Message