User talk:Wvbailey/Function definitions

test cases for article

f is a subset of u x v

the projection of f onto u concides with all of u

each element of u corresponds to exaclty one element of v —Preceding unsigned comment added by Wvbailey (talk • contribs) 22:00, 30 September 2007 (UTC)[reply]

∀z(z ∈ f ⇒ (∃u₁ ∃v₁ (u₁∈u ⋀ v₁∈v ⋀ "z = <u₁, v₁>")))

⋀ ∀u₁ (u₁∈u ⇒ ∃z(v1∈v ⋀ "z=<u₁,v₁" ⋀ z∈f))

⋀ ∀y₁ ∀v₁ ∀v₂ (∃z₁ ∃z₂ (z₁ ∈f ⋀ z₂ ∈f ⋀ "z₁ = <u₁, v₁>" ⋀ "z₂ ⋀ <u₁, v₂>" ) ⇒ v₁ = v₂

The following is a division algorithm that, in a counter machine, produces the quotient q in register (at location) Q and residue (remainder) r at location R, i.e. [Q] = q and [R] = r. Given an n in N, it computes: n = q + r/x.

" DEFINITION 1. x is a fraction ⇔ (∃m)(∃n)(n ≠ 0 & x = <m, n>) " (Suppes Axiomatic Set Theory 1972:162)

The relation ⋍_f is defined as follows:

m₁/n₁ ⋍_f m₂/n₂ ⇔ m₁n₂ = m₂n₂

" DEFINITION 38. x is a sequence if and only if x is a function on the set ω of natural numbers." (p. 174)

" DEFINITION 40. If x is a sequence, < x₁, x₂, . . ., x_n, . . .> = x (p. 174)

"Every real number can be uniquely represented by a non-terminating decimal [i.e. made of a string of integers]" (p. 189)

"THEOREM 56. Let r be an integer ≥ 2. Every real number x is uniquiely representable with respect to the radix r as a sequence <a, d1, d2, . . ., dn, . . .> such that

"(i) a is the largest integer equal to or less than x,

"(ii) for all n, 0 ≤ dn < r and dn is an integer,

"(iii) it is not the case that there is an N fsuch that for all n > N, dn = r - 1

"(iv) the sequence whose terms cn are defined recursively by

"c0 = a

"cn+1 = cn + dn+1/rn+1

"is a Cauchy sequence which converges to x. (ibid

A "Cauchy sequence" is one that converges:

DEFINITION 44. x is a Caucy sequence of real numbers if and only if x is a sequence of real numbers and for every real number e > 0, there is a positive integer N such that for every m,n > N

|x_n - x_m| < e "(ibid p. 175)

And finally,

" DEFINITION 60. If x is a sequence of real numbers and y is the limit of x then

" lim _n→∞ x_n = y "(ibid p. 185)

"Theorem 52. A sequence of real numbers has a limit if and only if it is a Cauchy sequence." (ibid p. 185)

The

	Address	Instruction	Register	If [A]=0 goto:	If [A] ≠ 0 goto	Action	Description
	1	clr	Q	2	2	0 → Q	; CLEAR: 0 => quotient
outer_loop:	2	clr	R	3	3	0 → R	; CLEAR: 0 => residue
restore_D:	3	ldA	X	4	4	[X] → A	; LOAD_A from X: restore input X to denominator D
	4	stA	D	5	5	[A] → D	; STORE_A in D: put contents of A into denominator A
inner_loop:	5	jz	D	10	6	( [D] = 0 )10+( [D] ≠ 0 )6	; test D for 0: IF D=0 then go to quotient+1 step 10 else step 6
	6	jz	N	11	7	( [D] = 0 )10+( [D] ≠ 0 )6	; test N for 0: IF N=0 then go to done step 11 else step 7
	7	dcr	D	8	8	[D] - 1 → D	;decrement denominator D
	8	dcr	N	9	9	[N] - 1 → D	;decrement numerator N
	9	inc	R	5	5	[N] - 1 → D	;increment residue, return to inner_loop for another round
quotient+1:	10	inc	Q	2	2	[Q] - 1 → D	;increment quotient, return to outer_loop
done:	11	H					;halt

Comments

What do any of the algorithms have to do with the definition of function? — Arthur Rubin | (talk) 16:37, 2 October 2007 (UTC)[reply]

I'm not sure yet, but I think the reasoning goes something like the following sequence of 10 steps. My sense is: an algorithm per se is probably not a function, but rather the rule behind the function. But the algorithm-function connection is this, i.e. that behind every function is an algorithm that can expressed in the form of a Turing machine. Or perhaps: every function is a Turing machine. Or something to that effect. With regards to any random assignment e.g. the little drawings in the Function (mathematics) article, these set-theoretic drawings can be simulated by a counter machine algorithm (which I intend to produce an example of).

About these silly random examples of useless mappings, Minsky points out: "No mention is made of what the rule really is [i.e. the set-theoretic relation that produces the function-set of ordered pairs]. (There might not even be one, though that leaves the uncomfortable question of what one could use the function for, or in what sense it really exists.)"(Minsky 1967:133). With regards to this issue, which I think is serious, it would seem that there is an implied problem with the axiom of specification if it is, in effect an expression of randomness. Halmos's version of the Axiom of Specification requires a specification (!):

"Axiom of Specification. To every set A and to every condition S(x) there corresponds a set B whose elements are exactly those elements x of A for which S(x) holds. ¶ A "condition" here is just a sentence." (Halmos 1970:6).

Suppes calls this "Aussonderung Axiom" the "Axiom schema of separation" and his version too requires "a property" that must be satisfied for the "assundering". But the nature of this "property" is unclear, in Suppes. But whatever, we can always write a Turing-machine algorithm that partitions any set of (expressible) numbers into any other two or more sets. And thereby the partitioning is a definite procedure (Zermelo 91929) says not... footnote in Suppes 1972:6).

The following is suggested by Minsky 1967:158, all that follows is my attempt to understand it better. Also if you are able, see the treatment of "function" in the Encyclopedia Britannica CD article, -- they start with rational function and develop from there.

Minsky analyzes the real numbers from the point of view of computation theory, in particular Turing machines. He suggests the use of Cauchy sequences. From there it's all down hill:

"§7.01. Functions of non-negative integers ... we will consider mainly a very special kind of rule -- namely, defining functions in terms of the behavior of Turing machines. " (Minsky 1967:158)

"9: THE COMPUTABLE REAL NUMBERS...a real number can be defined by an increasing or decreasing convergent infinite sequence of rationals. And it can be shown that, if the reals are suitably defined as equivalent classes of convergent sequences of rationals, we get the same structure as that defined by the cut method .... the definition by sequences is the method of Cauchy."(Minsky 1967:158)

The following is an attempt to understand the connection between the notion of "Turing machine", "function", and "algorithm", and "set theoretic notions e.g. of "ordered pair":

(1) We start with (one of two of) Minsky's definitions of "function" (1967:132), i.e. a Turing machine. Turing machines do algorithms. That is all they do. Some folks think of the Turing machine itself (TABLE and specifications for input-output) as the algorithm. I dunno; I'm agnostic. Minsky's other definition is the set-theoretic one. He gives examples of both, which I intend to ape when I get to it.

(3) A Cauchy sequence is a function in the set theoretic sense of ordered sequence (of ordered pairs) i.e. <a, x1, x2, ..., xn, ...> where the a and xi are all integers, and in the Minsky sense i.e. has an input and an output and some rule in between (Definitions is Suppes 1972:174) (Minsky 1967:132)

(3) A Cauchy sequence can be used to create any real number that is "algebraic"; non-algebraic numbers are "transcendental" (cf Hardy and Wright 1979:159 11.5 Algebraic and transcendental numbers). But some transcendentals can be created (calculated, computed), cf Turing 1936:142-143 where he shows that e.g. the transcendentals π and e are computable. "From (vi) we deduce that all real algebraic numbers are computable." And he proves this.

(4) Every real number is a Cauchy sequence (Theorem 43)

(5) A Cauchy sequence contains only integers (cf Suppes, Theorem 56 p. 189)

(6) A Turing machine/counter machine creates only positive integers from positive arguments; negative integers can be encoded e.g. by concatenating a "1" before its positive integer (e.g. this can be a definition, also see the next one)

(7) A Turing/counter machine can compute anything computable (Turing's Thesis cf Turing 1939), including all the primitive recursive functions such as addition of integers, subtraction of integers, products of integers and quotients (with residues) of integers (Kleene 1952:219ff). This is all the computing power that is necessary to create a Cauchy sequence.

(8) Therefore a Turing/counter machine can create any Cauchy sequence to any precision

(9) A counter machine is Turing-equivalent (Minsky 1955?, also Minsky 1967, also Boolos-Burgess-Jeffrey 2002)

(10) Therefore if a number can be created at all, by any manner shape or form, it can be created by a counter machine. And while in operation, a counter machine, like a Turing machine, is executing an algorithm' (or depending on your taste, perhaps: "is functioning as a function or perhaps: is functioning as an algorithm, or both).

Turing states that, and I believe him:

"We cannot define general computable functions of a real variable, since there is no general method of describing a real number, but we can define a computable function of a computable variable." (p. 140)

This is as far as I've been able to get in the couple days since this article spun off. I hope this answered your question.

References:

Alan Turing 1936:116ff in Davis 1965, The Undecidable, Raven Press, Hewlett NY
Alan Turing 1939:155ff in Davis (loc cit)
Patrick Suppes 1972, Axiomatic Set Theory, Dover Publications, Inc. New York.
Paul R. Halmos 1970, Naive Set Theory, Springer-Verlag, NY.
George Boolos, John Burgess, Richard Jeffrey 2002, Computability and Logic: Fourth Edition, Cambirdge University Press, Cambridge UK.
Marvin Minsky, 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.
Stephen C. Kleene, 1952, 1971 6th edition, 10th impression 1991, Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam NY
G. H. Hardy and W. M. Wright 1979, An Introduction to the Theory of Numbers: 5th Edition, Clarendon Press, Oxford UK.

wvbaileyWvbailey 19:16, 2 October 2007 (UTC)[reply]