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|?
Stathis Papaioannou
> Let me just recall what is a computable function from N to N. It is > function from N to N which is such that it is exist a finite way to > explain how to compute it in a finite number of steps on any natural > numbers. More precisely: f is computable if there is a language L such > that f admits a finite code/program/description/number explaining how > to compute f(n), in a finite time on any number natural n.> I will say that that a language L is universal, if all computable > functions from N to N admit a code in L.> > A weak form of Church thesis can be put in this way: there exists a > universal language.> > I will say a digital (or finitely describable) machine M is universal > if M can "understand" a universal language L, in the sense of being > able to compute any computable functions described in L (and thus all > given that L is universal) . In term of digital machine, Church thesis > becomes: there exists a universal digital machine.> > Now what is wrong with the following argument: if there is an universal > language or machine, the computable functions can be described by > finite description in that language, or program for that machine.> Such a set is obviously enumerable. There is a bijection between N and > the set of those descriptions:> > 1 f1> 2 f2> 3 f3> 4 f4> etc.> > So the following function g is well-defined by:> > g(n) = fn(n) + 1> > Then, to compute it on the number n (439 say), just generate the > description/program of f1 f2 f3 ... until fn, that is f439, apply it > on n to get fn(n), f439(439), and add 1 to get g(n) = fn(n)+1, that is > here: f439(439)+1.> But then g cannot be described in the language L! Why? Suppose g is > described by a code in the language L: then g belongs somewhere in the > list f1, f2, f3, f4, f5, .... Thus there would exist a number k such > that g = fk, and thus g(k) = fk(k); but g(k) = fk(k)+1. And thus> > fK(k) = fk(k)+1 (*)> > And fk(k) is a well defined number given that the fi are all computable > functions from N to N. So I can substract fk(k) on both sides of (*) > just above, and I get 0 = 1 (contradiction). So there is no universal > language, we cannot generate all computable functions, still less, > then, to dovetail on them.>
_________________________________________________________________
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 Thu Jun 15 2006 - 08:41:07 PDT