Re: [ALL] Homework for July 25 telecon

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