[CST-2] Opt Comp quick question

[Stephen McIntosh]

> y2001p8q7
>
> part b
>
> It seems to me that you can guarentee a_t+1 will not terminate when f does
> not terminate; and as the question emphasizes `safety' it's probably best
> to say no more.
>
> So do you really get 5 marks for writing down
>
> not f# => not a_{t+1}#
>
> or have I missed something big?

I think you've missed something...

b)
(n.b. % is "for all", <= is "less than or equal to" and e is "a member of")


f#     -> SAFE but not PRECISE
a_t+1# -> PRECISE - defined by compiler designer, hence no computability
                    problems.

%x1,...,xn e {0,1}
a_t+1#(x1,...,xn) <= f#(x1,...,xn)

where	0 <= 0
	0 <= 1	<- a_t+1# and f# give different answers in this case.
	1 <= 1

c) Consider f with abstract strictness funvtion f#

f#(0)  = 1
f#1 = 0

i.e. f#(x) = not(x)

>From definition of 0,1 this is a contradiction
(in terms of Turing machines + the halting problem)

=> If argument doesn't HALT, then f may HALT
and if argument may HALT, then f doesn't HALT.

=> f# is not computable
=> Standard interpretation f is not computable.

Any fn. including negation can be reduced to the form above
=> No strictness fn. including negation can be computed.

=========================
Stephen McIntosh.

www.stephenmcintosh.com