Bruno,
I'll rephrase the problem - let me know if I get it wrong. It is proposed that all the functions f with certain attributes "A" be enumerated in a list: f1, f2, f3 etc. It looks like "A" in the example under consideration means "all the computable functions", but in fact there is a further implicit restriction: the list can only contain all the computable functions which will fit into the labelling scheme chosen for the list. Now, when we say that g(k) is the kth function in the list +1, we are defining an apparently computable function that does not have a place on the list, since if g were the ith function on the list we would have fi(i)=fi(i)+1. However, this is only a contradiction if we say that the list contains all the computable functions; it is not a contradiction if we say that the list contains all the computable functions which fit into the labelling scheme chosen for the list, as I think we must. This is perhaps just the point you are making: it is not that g is not computable, rather that the attempt to enumerate the computable functions is problematic. But is it as surprising to discover this (or what I think of as related results, like Russell's Paradox and Godel's Theorem) as it would be to discover, say, a discrepancy or contradiction in the addition and subtraction of integers?
I'll reply to the second part of your post later.
Stathis Papaioannou> > I've always wondered (from a position of relative mathematical > > naivete, please understand)> > about the process in arguments like this whereby reasoning about > > arithmetic comes to> > include the labels applied to arithmetical statements, on the grounds > > that these labels happen> > themselves to be numbers. The function g as defined below is based on > > a look-up table, and > > the contradiction consists in that this table has the same label > > applied to more than one> > distinct value, i.e. fk(k) and fk(k)+1. Doesn't this just mean that > > the chosen labelling> > scheme is ill-chosen? Is there any way to separate f and g formally, > > perhaps to call g a> > meta-function (or something) rather than a function of f, and thus > > avoid the contradiction?> > Or is this whole train of thinking basically flawed, there being no > > method in general to> > banish g from the cosy world of functions like f(x)=x^2 or sin(x) or > > |x|?> > > Just two questions before I leave, the first concerns this current > thread, the second refers to an older post of you.> > Why do you think g is defined from a look-up table? G applied on n > generates the Fi when needed. g would like generate the fi but can't. I > am using the convention that the Fi are the programmable function (thus > the partial computable one), and the fi are the total computable > functions.>
_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE!
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Sat Jun 17 2006 - 01:57:53 PDT