One good turn.
" The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky,
that it is almost embarrassing to relate. His basic procedure is as follows:
1. Someone introduces Gödel to a UTM, a machine that is supposed to be a
Universal Truth Machine, capable of correctly answering any question at all.
2. Gödel asks for the program and the circuit design of the UTM. The program
may be complicated, but it can only be finitely long. Call the program
P(UTM) for Program of the Universal Truth Machine.
3. Smiling a little, Gödel writes out the following sentence: "The machine
constructed on the basis of the program P(UTM) will never say that this
sentence is true." Call this sentence G for Gödel. Note that G is equivalent
to: "UTM will never say G is true."
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. If UTM says G is true, then "UTM will never say G is true" is false. If
"UTM will never say G is true" is false, then G is false (since G = "UTM
will never say G is true"). So if UTM says G is true, then G is in fact
false, and UTM has made a false statement. So UTM will never say that G is
true, since UTM makes only true statements.
6. We have established that UTM will never say G is true. So "UTM will never
say G is true" is in fact a true statement. So G is true (since G = "UTM
will never say G is true").
7. "I know a truth that UTM can never utter," Gödel says. "I know that G is
true. UTM is not truly universal."
-----Original Message-----
From: Yasuki Arasaki [mailto:[log in to unmask]]
Sent: Thursday, January 12, 2006 5:21 PM
To: [log in to unmask]
Subject: Re: function v.s. subroutine
Richard Wang wrote:
> For example, is there a general guideline for using function and
> subroutine. I heard a least in one case, when the return object is an
> array, subroutine is more efficient because it doesn't generate an
> extra copy of array. Are there any other concerns?
This doesn't directly answer your question, but I'd like to point out a
general concern before thinking of efficiency (and you probably have thought
of all this..).
I usually use FUNCTIONSs only for mathematical functions and logical
functions depending on its arguments. This is just my preference and not
really for efficiency. I would like to think that A FUNCTION computes
something from something, a SUBROUTINE does something to something, although
I know that at a lower level of abstraction those two mean the same thing to
the computer.
So, IS_UPPERCASE(CHAR) I code as a function, but
TO_UPPERCASE(STRING) is a subroutine to me, even though it has only one
result value and could be written as a function. I want all the characters
in STRING converted to uppercase, not that I want to compute some value from
STRING.
The intrinsic function TRANSPOSE is rightly a function, but if I had a 2D
array that represents some image and holds pixel values, and need to code a
procedure to make its mirror image along a diagonal line, I'll code that as
a subroutine (even if I needed to preserve the original array). If I needed
a procedure that computes some color average of the same image array, that's
a function. If the procedure is to compute a "fingerprint" vector from the
image array, that's a function, although it may return an
array. If the procedure is to do a "fingerprint analysis" on the image
(whatever that is), that's a subroutine, although it may do exactly the same
thing as the fingerprint function.
--
Yasuki Arasaki
[log in to unmask]
|