About Lab6

[Zuo Zeng]

In Question 8(a), the latter set {x:W_x=\varnothing} is not r.e. and
cannot be T-complete. It was meant to be {x:W_x\neq\varnothing}, is it?

[js05212]

+1

 

2012-05-30

---

js05212

---

发件人：Zuo Zeng

发送时间：2012-05-27 12:55

主题：About Lab6

收件人："sjtu_cs363"<sjtu_...@googlegroups.com>

抄送：

[Xiaofeng Gao]

Yes. For T-reduction, {x:W_x=varnothing} and {x:W_xneqvarnothing} are
equivalent, but to satisfy "A is r.e.", the set should be
{x:W_xneqvarnothing}.

Thank you.

---
-----------

Sincerely Yours,

Xiaofeng Gao, PH.D.（高晓沨）
Assistant Professor
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Email: gao...@cs.sjtu.edu.cn
Office: Telecom Bldg 3-543 Phone: 021-34207407

On Wed, 30 May 2012 21:40:11 +0800, js05212 wrote:
> +1
>
> 2012-05-30
>
> -------------------------
>
> js05212
>
> -------------------------
>
> Zuo Zeng
> 2012-05-27 12:55
> About Lab6
> "sjtu_cs363"
>
> In Question 8(a), the latter set {x:W_x=varnothing} is not r.e. and
> cannot be T-complete. It was meant to be {x:W_xneqvarnothing}, is it?

[Guobao Sun]

In Question 9(a)
$A\equiv_T B$ iff $K^A\equiv_m K^N$ ?
What is N....I guess it should be K^B?

[Xiaofeng Gao]

You're corrected. It should be K^B. Thanks.

---
-----------

Sincerely Yours,

Xiaofeng Gao, PH.D.（高晓沨）
Assistant Professor
Department of Computer Science and Engineering
Shanghai Jiao Tong University
Email: gao...@cs.sjtu.edu.cn
Office: Telecom Bldg 3-543 Phone: 021-34207407

On Sun, 03 Jun 2012 11:15:38 +0800, Guobao Sun wrote:
> In Question 9(a)
> $Aequiv_T B$ iff $K^Aequiv_m K^N$ ?

> What is N....I guess it should be K^B?
>
> On 2012/5/31 14:31, Xiaofeng Gao wrote:
>
>> Yes. For T-reduction, {x:W_x=varnothing} and {x:W_xneqvarnothing}
>> are equivalent, but to satisfy "A is r.e.", the set should be
>> {x:W_xneqvarnothing}.
>>
>> Thank you.
>>
>> ---
>> -----------
>>
>> Sincerely Yours,
>>
>> Xiaofeng Gao, PH.D.（高晓沨）
>> Assistant Professor
>> Department of Computer Science and Engineering
>> Shanghai Jiao Tong University

>> Email: gao...@cs.sjtu.edu.cn [1]

>> Office: Telecom Bldg 3-543   Phone: 021-34207407
>>
>> On Wed, 30 May 2012 21:40:11 +0800, js05212 wrote:
>>
>>> +1
>>>
>>> 2012-05-30
>>>
>>> -------------------------
>>>
>>> js05212
>>>
>>> -------------------------
>>>
>>> Zuo Zeng
>>> 2012-05-27 12:55
>>> About Lab6
>>> "sjtu_cs363"
>>>
>>> In Question 8(a), the latter set {x:W_x=varnothing} is not r.e.
>>> and
>>> cannot be T-complete. It was meant to be {x:W_xneqvarnothing}, is
>>> it?
>
>
>

> Links:
> ------
> [1] mailto:gao...@cs.sjtu.edu.cn