Understanding Formal Math: Explaining Turing Machines in Simple Terms

[samh]

PLEASE help me understand this paper! (Formal math stuff)

Right now in my class we're being given a short introduction to theoretical CS. We're learning not from a book but from our teacher's Ph.D. thesis! The thesis is HEAVY on formal math and I can't follow it... I've been trying for DAYS and have spent many, many hours reading around but it's not making sense. I'm officially desperate now and so I've come here to ask if I could possibly get some help from you guys.

Here's the part I'm stuck on, it's about Turing machines:

http://img105.imageshack.us/img105/5915/help27ib.th.jpg

I've been reading a lot and I now understand the distinction between an Urelement and natural numbers as defined with sets (with the axiom of infinity). It's the rest of the paper that I don't get. If any of you could explain to me what the paper is saying possibly with some examples (especially of the Sq thing) then I would be very greatful. If you're pressed for time then here are the parts I'm most confused about:

• What does the Sq_(w)(A) thing mean?? If A is, say, { a, b, c }, then what would Sq_(w)(A) be? Can you lay it out for me (i.e. write out the elements of the set in set notation { ... })?
• In the definition part, when it says "Let A be a set, u, v in Sq_(w)(A)" what does that really mean? If something is an element of Sq_(w)(A) then what does it look like?

 

[StatusX]

Aⁿ is the set of all n-tuples of elements of A, ie, ordered sets of n elements from A. For example, if A=R, the set of real numbers, then Rⁿ is just n-dimensional Euclidean space (you're probably familiar with this as a vector space, although here it is just a set, with no extra structure). For example, (1,2,6) is an element of R³.

Sq_(w)(A) is the union of the Aⁿ for n=0,1,2,... In other words, it is the set of lists of elements of A of any finite length. (1), (1,2,3), and (12,12,12,12,12) are all elements of Sq_(w)(R).

 

[AKG]

No, ⁿA is the set of lists of elements of A of size n, Aⁿ is the set of functions from n = {0, 1, ..., n-1} to A. Of course, there is a natural bijection between the two, but ⁿA never really comes up on that page, except when it is defined. Sq_(w)(A) is the union of all Aⁿ, so it is the set of all functions from a natural number to A. If u, v are in Sq_(w)(A), then u and v are functions, each whose domain is a natural number (although u and v need not have the same domain) and both of whose codomain is A.

So if A is {a,b,c}, and u is an element in Sq_(w)(A), then u is a function u : n -> A where n is some natural number. If n were 5, say, then u could be the function defined by:

u(0) = u(1) = u(2) = u(4) = c; u(3) = b

In general, a function from X to Y can be written as a set of ordered pairs, where for each x in X, there is a unique y in Y such that (x,y) is in this function. For example, the squaring function on the reals is the set:

{(x,x²) | x in R}

So the function u above could be written as:

u = {(0,c), (1,c), (3,b), (3,b), (2,c), (4,c)}

Note that the repetition of (3,b) has no significance, nor does the order of the elements of u, so u could have been written as you'd expect to see it:

u = {(0,c), (1,c), (2,c), (3,b), (4,c)}

 

[samh]

Sq_(w)(A) is the union of the Aⁿ for n=0,1,2,...

Sq_(w)(A) is the union of all A_n, so it is the set of all functions from a natural number to A.

I don't get it... The paper says ⁿA but StatusX is saying Aⁿ and AKG is saying A_n. Is there something I'm missing?

Edit:

I see now! AKG what you're saying is now making sense to me. Sq_(w)(A) is an infinite set of functions. Therefore u and v being members of Sq_(w)(A) means that they themselves are functions too, and that set of ordered pairs is actually a function specification. And now I see what they mean by u(0) since u is actually a function. After all this time it finally makes sense... Thanks guys.

 

[AKG]

Sorry, A_n was a typo, I meant Aⁿ. Anyways, it seems like you understand it now.