How can we know the coding function \alpha(x):Z->N is computable?
Jiteng Hao
is computable without coding. However, how can we say alpha is
computable?
Furthermore, can we say that f(x)={1,if M(x) holds; 0, if M(x) not
holds.} is computable if M(x) is decidable?
Thank you!
Xuangui Huang
For Prob2, the definition of decidability of M(x) rely on the computability of its characteristic function c_M(x) which turns out to be the same as your f(x). Maybe it's just the dependency of our definition. We define computability of functions first, then define decidablity of predicates.
For Prob1, I have no ideas about it. What I've known is that \alpha is just a coding, kind of reduction. And perhaps our universal domain of computability funtions is natural numbers, so we can't discuss the computability of functions map Z to N?
Hope it will help you.
(Hsüan-kui Huang)
Department of Computer Science and Engineering,
Xiaofeng Gao
You can use "definition by cases" and "algebra of decidability" to show
the computability of \alpha(x) (also this can answer your second
question). According to the definition of computability from our
textbook, what we are discussing is some functions with the same domain
and range (e.g., N->N, or Z->Z, D->D), and thus f*=\alpha f \alpha^{-1}.
For our homework, we are dealing with a special case f:Z->N. At this
time it is both fine to give f*=\alpha f \alpha^{-1} (meaning you're
considering Z->Z), or you can take off one \alpha from f* (meaning
you're considering Z->N). Also, for this question, I'm trying to ask you
two questions: (1) prove 'x is even' on N; (the URM program design) and
(2) prove 'x is even' on Z (the coding function). They are independent.
(Next time I'll make the description more clear).
---
-----------
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, 29 Feb 2012 14:25:16 +0800, Xuangui Huang wrote:
> In my opinion,
> For Prob2, the definition of decidability of M(x) rely on the
> computability of its characteristic function c_M(x) which turns out
> to
> be the same as your f(x). Maybe it's just the dependency of our
> definition. We define computability of functions first, then define
> decidablity of predicates.
> For Prob1, I have no ideas about it. What I've known is that alpha
> is
> just a coding, kind of reduction. And perhaps our universal domain of
> computability funtions is natural numbers, so we can't discuss the
> computability of functions map Z to N?
> Hope it will help you.
>
>
> Yours Sincerely,
> Xuangui Huang
> (Hsüan-kui Huang)
>
> Department of Computer Science and Engineering,
>
> School of Electronics, Information and Electrical Engineering
> Shanghai Jiao Tong University
> 800 Dong Chuan Road, Minhang District, Shanghai 200240, China
> Tel: +8618801902110
> Email: sts...@gmail.com [1]
>
> On Wed, Feb 29, 2012 at 12:54 PM, Jiteng Hao wrote:
>
>> Our discussion only focus on N, and we can only prove a function on
>> N
>> is computable without coding. However, how can we say alpha is
>> computable?
>> Furthermore, can we say that f(x)={1,if M(x) holds; 0, if M(x) not
>> holds.} is computable if M(x) is decidable?
>>
>> Thank you!
>
>
>
> Links:
> ------
> [1] mailto:sts...@gmail.com
> [2] mailto:phoeni...@gmail.com