- From: Francois Bry <bry@ifi.lmu.de>
- Date: Wed, 26 Jul 2006 08:51:51 +0200
- To: "Public-Rif-Wg (E-mail)" <public-rif-wg@w3.org>
Dear RIFler, Following Markus good and well explained views, and in an attempt to summarize what he suggested, I suggest to rephrase the questions as follows: Rephrase: ... * Is your language Turing-complete? * Is your language decidable? * Is your language semi-decidable? * Other expressivity/decidability results (specify)into Specify expressivity of your language by describing the class of expressible computations and/or the difficulty of typical inferencing tasks. Give details in the text field below if it is not obvious what computation/inference task you refer to. Please also give more specific complexity results (e.g. hardness, membership, completeness) if available. * Is the rule language Turing complete? * Is inferencing for your language decidable? * Is inferencing for your language semi-decidable (in case it is not decidable)? * Is inferencing for your language not semi-decidable? * Other expressivity/decidability results (specify) Concerning the following point made by Markus, I think refering to Turing completeness is sufficient. To the best of my understanding, both questions Markus mentions (cf. infra) are equivalent. > So I wonder whether there we have any shared understanding about the meaning > of "Turing-complete" in the above question. Do we mean > > * "somehow able to simulate the computation of any Turing machine" > > or, more strictly, > > * "using rules to represent functions, and being able to represent (at least) > all Turing-computable functions"? > Regards, Francois
Received on Wednesday, 26 July 2006 06:52:12 UTC