Re: [ALL] Homework for July 25 telecon

On Tuesday 25 July 2006 15:48, Francois Bry wrote:
> Dear RIFler,
>
> Hier are a few comments to Axel's very good proposal:
> > Axel's proposed RIFRAF questionnaire (for evaluating/populating the
> > framework): [http://www.w3.org/2002/09/wbs/38457/RAFQuestionnaire/]
>
> The following question under 3.1 seems to me ambigous: "Is your language
> decidable?" Decidability of a language usually means, at least in
> theoretical Computer Science, that whether a word (= program) belongs to
> the language is decidable.This is the case for all programming and
> modelling languages. My understanding is that Axel would like to ask
> instead whether the termination of programs is decidable.

I agree. Since there was some confusion in the July 25 telco, here is some 
clarification and a proposal for fixing this.

(1) "Deciding a language" is an established term in (theoretical) Computer 
Science. It means: "deciding whether some word belongs to the language" (you 
may have encountered this meaning if you ever heard about regular, 
context-free etc. grammars).

(2) "Decidability of some logical or computational formalism" usually refers 
to some *inference problem* or *reasoning task* for the language. So you do 
not "decide the formal (rule) language", but you decide some inference 
problem related to this language. [Side remark: of course this can also be 
comprehended as deciding some related "language" in a Computer Science sense, 
but this is not relevant here.]

So every language we deal with is probably decidable in the sense of (1). What 
we are interested in the questionaire is whether its "main" inference problem 
is decidable in the sense of (2). The problem was that the wording of 3.1 is 
ambiguous about the fact that we mean (2) and that it does not say which 
computation/reasoning task we are really interested in when asking for 
complexity and decidability. So it is necessary to add some small note to 3.1 
to clarify what decidability (and also the other items) refer to.

I think this could be sufficiently fixed by changing the original text

"""Specify Expressivity of your language, e.g. Turing-completeness, or 
complexity classes for decidable languages. Please give complexity results if 
availbale (hardness, membership, completeness)

    * Is your language Turing-complete?
    * Is your language decidable?
    * Is your language semi-decidable?
    * Other expressivity/decidability results (specify)
"""

to 

"""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 formalism Turing-complete?
    * Is inferencing for your language decidable?
    * Is inferencing for your language semi-decidable (but not decidable)?
    * Other expressivity/decidability results (specify)
"""

Precision comes at the price of a more complicated wording here, since we have 
to account for Turing-completeness and for (semi-)decidability. Read on for 
some thoughts on this issue. Anyway, the above completes my ACTION from telco 
July 25.


------


As a second remark, I suggest to add one item
   
    * Is inferencing for your language not even semi-decidable?

since this applies to some of the discussed rule-languages (e.g. WRL) as well, 
and it would otherwise not be obvious what to answer in such a case. 


------


Thirdly, another remark emerges from the above suggestion. We apparently ask 
for different things when putting "Turing-completeness" 
and "semi-decidability" into one question. 

* Turing completeness refers to the ability of a formalism to express certain 
functions (actually: all "algorithmically computable" partial functions).

* Semi-decidability refers to the difficulty of answering certain 
yes/no-questions (e.g. the question whether something is entailed by a rule 
spec). Semi-decidability of such a task asserts that, whenever the answer 
is "yes", this answer can be computed. It does not assert anything for the 
cases where the answer would be "no".

Turing-completeness is related to semi-decidability via the halting problem 
that Francois mentioned. The yes/no-question there is: "Will the formalism 
ever return a result for this input?" (recall that we may compute *partial* 
functions as well). So Turing-completeness typically applies to formalisms 
that compute something, and in this case is mostly synonymous with 
semi-decidability of the halting problem.

On the other hand, expressive logics can also (indirectly) describe 
computations on Turing machines, and thus might be considered Turing-complete 
in this sense. 

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"?

The first is mostly synonymous with being semi-decidable, the second combines 
aspects of expressivity with the question *what* actually is expressed. 
Neither is really desirable here. I therefore would suggest to make 
Turing-completeness less prominent by making it a sub-case of the item for 
semi-decidability (possibly giving the same wording as above, but sharing one 
check-box with semi-decidability). This should yield the same (and probably 
more consistent/accurate) information about the classified rule language, but 
it eliminates the different combinations of answers that could otherwise 
occur.


Regards,

Markus


>
> Convcering 3.2, I would suggest ot ask whether the model theory is
> defined in a Tarskyan style, i.e. by means of a valuation function
> recursively defined on a formulas (or program  expression) strucure like
> classical logic models or by some other manes like well-founded or
> stable models. This distinction is essential for the evaluation of a
> rule-based language. Basically: rule languages with a Tarskyan model
> theory are "easy" to evaluate.
>
> I would suggest to add a question whether the language has means to
> access data in Web formats such as HTML, XML, RDF, OWL data.
>
> Regards,
>
> Francois

-- 
Markus Krötzsch
Institute AIFB, University of Karlsruhe, D-76128 Karlsruhe
mak@aifb.uni-karlsruhe.de        phone +49 (0)721 608 7362
www.aifb.uni-karlsruhe.de/WBS/     fax +49 (0)721 693  717