Any computer user knows that, form time to time, a piece of software gets stuck, "crashing" into an endless loop of calculations, and making the computer unable to perform any other tasks. If a human user notices the computer in such a state, she will usually try to abort the task, sometimes simply by restarting the computer. Because getting into infinite tasks can drastically curtail a computer's effectiveness, operating systems and program compilers will often have checks, looking for tell-tale signs that a program might get stuck. But by a well-known theorem no such checks are perfect.
The proof of this theorem is easy. Say a program H can look at any piece of software and decide, yes or no, whether that software will eventually halt. Software can occasionally take input; perhaps H should be a function of two variables, the string encoding the software S, and the string encoding the input T: H = H(S,T). We can modify this into a new function G(S) = H(S,S), with just a few extra lines telling H that whenever it wants to look at T, actually look at the single piece of input S — i.e. G asks whether S will halt when it acts on itself. Then apply an easy alteration to G, making it less useful: if the answer is yes, rather than saying so, just start counting numbers starting at 1 and going forever. Now apply G to itself, and while you're waiting, perhaps you should get a haircut from the Barber of Seville.
However, none of this takes into consideration the actual facts of real computers. A computer is not, however much we'd like to model it as such, an idealized Turing machine. Its (finite) memory and speed depends such variables as what brand it is, and when it was built.
It is this last observation — that computers are getting faster — that allows us a solution to the Halting Problem. Computers are not just getting faster; they're getting faster exponentially. For some constant C > 1, the number of calculations one of next year's computers can perform in a minute will be at least C times faster than the number of calculations one of this year's computers can perform in a minute.
Thus, rather than run a program we expect to take a long time (if it doesn't halt, it will probably take at least a year) on just one computer, let's set up a fancy server farm, and swap out old computers for new ones. Now, let's hope that Moore was wrong, and that computer speeds grow slightly faster than he predicted, for the following reason: next year's computer, being C times as fast, has 1/C the life-span, and a new C-times better computer is released not at the end of another year, but after just 1/C of a year.
So, this year, we perform some number of calculations N, on our computers. Next year, we get a C-times better computer, but only have it for 1/C as long, so perform another N calculations. Then we get a C^2 computer, and have it for 1/C^2 years. Etc. After infinitely many iterations of this, we've performed N+N+N+... = infinitely many calculations. But our total time spent? 1+1/C+1/C^2+... = C/(C-1) < infinity.
So our algorithm to solve the Halting Problem? Eventually, we will have computers that can totally automate their own server-farm swapping and growing and building (so we really will be able to swap out old for new parts arbitrarily fast). So let's program on of these to do that — to build itself at the predicted exponential rate. And while it's doing so, run whatever program we want to know about. If in less than C/(C-1) time the program stops, then we know it will stop and after how many calculations, and even what the outcome will be. And if it doesn't, then we get the other answer.
30 May 2007
13 May 2007
What functions do we need for physics?
If any physicist asked to use any particular function, I would never begrudge it of her. Absolutely, if a particular mathematics is useful in calculating something about the world, by all means take advantage of it. But over the entire history of humanity we will never write down even countably many functions, and it's unlikely that any physical theory will ever require more than countably many (mathematical theories do so all the time). Moreover, it's unlikely that the physicists will ever need even easily-definable pathological functions like Weierstrass'. A fruitful way for mathematicians to help physicists is by suggesting which conditions are reasonable to assume of any theory, and which should be explored: one such question is to ask for an "upper bound" — a collection of functions that the physicists are unlikely to ever need to escape.
Of course, "real-valued functions on a real line" is one possible answer, but the whole point is that we're likely to find a better bound. Most physicists seem to believe that the universe satisfies some sort of continuity or regularity conditions, and most physicists leave such issues aside when writing their actual arguments; at the very least, I've never seen a physicist to want a function that it discontinuous at more than discretely many points. This again, though, is not all together helpful. Hoepfully, we will get down to countably many functions (or, possibly, a class of functions defined with reference to an as-yet-to-be-determined class of coefficients, so that if our possible coefficients are countably many, then so are our functions), and we're no where near there. A big step is to remind ourselves that physicists certainly will never need more than the definable functions. Still, this definition allows such functions as Weierstrass', and is terribly inductive: it would be nice to have a closed-form definition of the set in question.
What are the tools a physicist is likely to want in writing down a physical theory? It's reasonable to expect our functions to include all the constant functions, and the identity. Moreover, our set of functions should be closed under addition, subtraction, multiplication, and division. This should lead to no complaints — so far, we could stop just with rational functions.
I think, though, that every function should have an inverse (away from singularities, of course — given an allowed function and an open ball in which the function has (in the classical sense) an inverse, this inverse should also be an allowed function). Again, no problem — we can allow all algebraic functions — although now we already escape the realm of good notation (c.f. Abel's Theorem). And our class of allowed functions should be closed under composition. (Question: is the composition of two algebraic functions algebraic? By algebraic function I mean a solution y=y(x) to a polynomial equation 0=F(x,y).)
Thing is, though, we don't yet have the functions physicists use most often: the exponential and trigonometric functions. This must absolutely be fixed. Why do physicists use these? Because they solve simple differential equations.
Indeed, I don't know any functions that appear in physics that do not solve polynomial differential equations, by which I mean equations of the form 0=F(x,y,y',...). In fact, although physicists use second-order equations all the time, I have a hard time coming up with any equations that are not first order (and, of course, if we allow multiple variables, then all differential equations can be cast as first-order). This leads me to suggest that an appropriate answer to the question posed by this post is "solutions to polynomial differential equations".
Does this class of functions possess the properties I want? Certainly it includes algebraic, exponential, and trigonometric functions, and consists only of extremely smooth definable functions. And it's easily closed under inverses. To wit: given an equation 0=F(x,y,y',...) and solution y=y(x), I'm looking for an equation 0=G(y,x,x',...) for which x=x(y) is a solution (where x() is the inverse function of y(), and x'=dx/dy); it suffices, of course, to find a rational function G. But we can let G(y,x,x',...) = F(x,y,1/x',...), since by easy calculus y'=1/x', and by induction higher-order derivatives or y are also rational functions of the derivatives of x:
y^{(n)} = d(y^{(n-1)})/dx = 1/(dx/dy) d/dy [y^{(n-1)}]
But when we start to ask about the binary operations — arithmetic and composition — we see that disaster strikes. Composition is the easiest to visualize, and I will restrict to first-order ODEs.
A differential equation is a surface in 1-jet space
{0=F(x,y,y')} \subseteq \J^1(\R)
(where I use \J for {\cal J} and \R for {\mathbb R}). 1-Jet space, for us, is just \R^3 parameterized by coordinates x, y, and y'; more generally, it's the cotangent bundle cross \R. It comes equipped with a canonical contact structure 0 = dy - y' dx. When this contact structure is not tangent to the surface (a contact on \R^3 structure cannot be tangent to a surface at more than a curve), it defines curves that foliate the surface, so in small balls around generic points, solutions to the differential equation exist and are unique.
So, let's say I have to differential equations 0=F(x,y,y') and 0=G(y,z,z') and solutions y=y(x) and z=z(y) (where I'm thinking of z'=dz/dy). Then I really want a differential equation 0=H(x,Z,Z') so that Z(x)=z(y(x)) is a solution. And I'd like to be able to pick this H in some algorithmic way.
But the geometry makes this hard. Generically, what I'm setting up is a five-dimensional space with coordinates x,y,y',z,z' (or equivalently Z'=y'z'). I have surfaces in each of two three-spaces that intersect on a line. Then what in the five-space would project to two surfaces? A three-manifold. (Away from non-generic points, the surfaces are parameterized by y and another variable perpendicular to y, with a third variable running perpendicular, so the lift should be parameterized by y and two more perpendicular dimensions, with two dimensions of normal bundle.) But, generically, a three-manifold projects to a three-space in the x,Z=z,Z'=z'y' direction.
Because a first-order equation is two-dimensional, it takes one ordered pair of data (e.g. a value for x_0 and y_0=y(x_0)) to specify the particular solution. But the composition of two differential equations takes an ordered triple of data. (For comparison, the composition of two equations F(x,y)=0=G(y,z), which is what we use to compose functions, can be visualized as the quest for a lift to \R^3 of curves living in the xy- and yz-planes.) Perhaps the composition is a second-order differential equation? But our canonical three-surface does not have any Z''-direction, so this is impossible.
For the other arithmetic operations, a similar dimensional analysis occurs: we'd have two surfaces in 1-jet space, which we can think of as two fields of curves in the \R^2 bundle over the x-axis. But there's not a natural way to add, say, two curves to get another curve: with two generic curves on the plane (as opposed to two generic points), there's a whole surface worth of points that are the sum of some pair of points, one on each curve.
But this all leaves open the other version of the question. I've shown that there's no way to compose or add two generic differential equations. What I haven't answered is if the sum or composition of any two given solutions to differential equations is itself a solution to some differential equation. Probably I won't be satisfied even if it is, because I want all of physics to be definable, and I really want these differential equations (along with initial data) to _be_ the definitions of the functions. But nevertheless I cannot think of how to begin looking for a pair of functions, each solutions to polynomial differential equations, whose composition is not.
Of course, "real-valued functions on a real line" is one possible answer, but the whole point is that we're likely to find a better bound. Most physicists seem to believe that the universe satisfies some sort of continuity or regularity conditions, and most physicists leave such issues aside when writing their actual arguments; at the very least, I've never seen a physicist to want a function that it discontinuous at more than discretely many points. This again, though, is not all together helpful. Hoepfully, we will get down to countably many functions (or, possibly, a class of functions defined with reference to an as-yet-to-be-determined class of coefficients, so that if our possible coefficients are countably many, then so are our functions), and we're no where near there. A big step is to remind ourselves that physicists certainly will never need more than the definable functions. Still, this definition allows such functions as Weierstrass', and is terribly inductive: it would be nice to have a closed-form definition of the set in question.
What are the tools a physicist is likely to want in writing down a physical theory? It's reasonable to expect our functions to include all the constant functions, and the identity. Moreover, our set of functions should be closed under addition, subtraction, multiplication, and division. This should lead to no complaints — so far, we could stop just with rational functions.
I think, though, that every function should have an inverse (away from singularities, of course — given an allowed function and an open ball in which the function has (in the classical sense) an inverse, this inverse should also be an allowed function). Again, no problem — we can allow all algebraic functions — although now we already escape the realm of good notation (c.f. Abel's Theorem). And our class of allowed functions should be closed under composition. (Question: is the composition of two algebraic functions algebraic? By algebraic function I mean a solution y=y(x) to a polynomial equation 0=F(x,y).)
Thing is, though, we don't yet have the functions physicists use most often: the exponential and trigonometric functions. This must absolutely be fixed. Why do physicists use these? Because they solve simple differential equations.
Indeed, I don't know any functions that appear in physics that do not solve polynomial differential equations, by which I mean equations of the form 0=F(x,y,y',...). In fact, although physicists use second-order equations all the time, I have a hard time coming up with any equations that are not first order (and, of course, if we allow multiple variables, then all differential equations can be cast as first-order). This leads me to suggest that an appropriate answer to the question posed by this post is "solutions to polynomial differential equations".
Does this class of functions possess the properties I want? Certainly it includes algebraic, exponential, and trigonometric functions, and consists only of extremely smooth definable functions. And it's easily closed under inverses. To wit: given an equation 0=F(x,y,y',...) and solution y=y(x), I'm looking for an equation 0=G(y,x,x',...) for which x=x(y) is a solution (where x() is the inverse function of y(), and x'=dx/dy); it suffices, of course, to find a rational function G. But we can let G(y,x,x',...) = F(x,y,1/x',...), since by easy calculus y'=1/x', and by induction higher-order derivatives or y are also rational functions of the derivatives of x:
y^{(n)} = d(y^{(n-1)})/dx = 1/(dx/dy) d/dy [y^{(n-1)}]
But when we start to ask about the binary operations — arithmetic and composition — we see that disaster strikes. Composition is the easiest to visualize, and I will restrict to first-order ODEs.
A differential equation is a surface in 1-jet space
{0=F(x,y,y')} \subseteq \J^1(\R)
(where I use \J for {\cal J} and \R for {\mathbb R}). 1-Jet space, for us, is just \R^3 parameterized by coordinates x, y, and y'; more generally, it's the cotangent bundle cross \R. It comes equipped with a canonical contact structure 0 = dy - y' dx. When this contact structure is not tangent to the surface (a contact on \R^3 structure cannot be tangent to a surface at more than a curve), it defines curves that foliate the surface, so in small balls around generic points, solutions to the differential equation exist and are unique.
So, let's say I have to differential equations 0=F(x,y,y') and 0=G(y,z,z') and solutions y=y(x) and z=z(y) (where I'm thinking of z'=dz/dy). Then I really want a differential equation 0=H(x,Z,Z') so that Z(x)=z(y(x)) is a solution. And I'd like to be able to pick this H in some algorithmic way.
But the geometry makes this hard. Generically, what I'm setting up is a five-dimensional space with coordinates x,y,y',z,z' (or equivalently Z'=y'z'). I have surfaces in each of two three-spaces that intersect on a line. Then what in the five-space would project to two surfaces? A three-manifold. (Away from non-generic points, the surfaces are parameterized by y and another variable perpendicular to y, with a third variable running perpendicular, so the lift should be parameterized by y and two more perpendicular dimensions, with two dimensions of normal bundle.) But, generically, a three-manifold projects to a three-space in the x,Z=z,Z'=z'y' direction.
Because a first-order equation is two-dimensional, it takes one ordered pair of data (e.g. a value for x_0 and y_0=y(x_0)) to specify the particular solution. But the composition of two differential equations takes an ordered triple of data. (For comparison, the composition of two equations F(x,y)=0=G(y,z), which is what we use to compose functions, can be visualized as the quest for a lift to \R^3 of curves living in the xy- and yz-planes.) Perhaps the composition is a second-order differential equation? But our canonical three-surface does not have any Z''-direction, so this is impossible.
For the other arithmetic operations, a similar dimensional analysis occurs: we'd have two surfaces in 1-jet space, which we can think of as two fields of curves in the \R^2 bundle over the x-axis. But there's not a natural way to add, say, two curves to get another curve: with two generic curves on the plane (as opposed to two generic points), there's a whole surface worth of points that are the sum of some pair of points, one on each curve.
But this all leaves open the other version of the question. I've shown that there's no way to compose or add two generic differential equations. What I haven't answered is if the sum or composition of any two given solutions to differential equations is itself a solution to some differential equation. Probably I won't be satisfied even if it is, because I want all of physics to be definable, and I really want these differential equations (along with initial data) to _be_ the definitions of the functions. But nevertheless I cannot think of how to begin looking for a pair of functions, each solutions to polynomial differential equations, whose composition is not.
12 May 2007
Some politics
Polling data, a year and a half before the election, has almost no information in it. Then again, neither do those talking heads, and folks like me don't know anything either, and that's never stopped me from spouting ideas. So:
RealClearPolitics reports that, at present, Giuliani wins the GOP nomination (he's at 28% nationally; McCain is next at 20%; McCain, though, wins Iowa and New Hampshire, and Intrade is leaning towards McCain). The Democrats have fewer top contenders, and Clinton flies by with 35%, although the most recent Rasmussen poll has Obama almost tying. Gore is currently leading Edwards.
These polls are of "likely voters", and ask questions close to "if the election were help today, for whom would you vote". The more fun, and even less useful, polls are the head-to-head races, asking those polled to pick which of a particular Democrat and a particular Republican. In those, Obama currently edges by Giuliani, who squeezes past Clinton, who barely wins against McCain. Edwards does the best of leading candidates; Romney does the worst. (This is interesting: OnTheIssues has Edwards the most liberal of all of them, and Clinton and Obama exactly tied.)
I'm actually really excited about Giuliani winning the Republican nomination. He's pro-choice, and supports civil unions; he would pull the party to the left. I'm ecstatic about the idea of having two pro-choice parties in this country.
Of course, that likely means he wins the White House. This I'm not entirely unhappy with: if we lose Congress, then any Republican President would be disastrous, but provided we keep the legislative branch, we'd be able to work with Giuliani. He would not veto our social agenda, and we'd work with him on the economy — hell, Pelosi managed to work out trade bills and budgets with the current President, and these days Demorats are more fiscally conservative than Republicans. I think the country works well when we have different parties in power, and a Giuliani presidency would be a staunch repudiation of the Basest of Republicans.
Then again, perhaps he doesn't win. If spun correctly, this is still a critique of the ultra-right: the rightists nominated him, and couldn't even make good. But their spin machines are better than ours, and I worry that Giuliani losing looks more like a failure to energize the Base — it almost strengthens the ultra-right.
I still think that Clinton, of all the candidates in either party, would make the best President. She's brilliant, and extremely experienced in so many things. But will she surmount her negatives? Thirty percent of Americans right now say that they will never vote for her under any circumstances. Put her alone in a room with her and she'll win them over, of coruse — look at what she's done to Newt Gingrich and other Congressional rightists who used to abhor her. But that's not how elections are won.
Then again, I wonder if she might be the only Democrat who actually stands a chance. Her campaign machine is intense; the NYTimes reports that her husband will, come Fall, start doing campaign stops for her, and for now is bringing in over $100,000 a night fundraising. He plans to win, for her, Arkansas, Kentucky, Louisiana, and Florida.
More than that, Clinton is the only person whom I believe could withstand a Swift Boat attack. The best thing for Obama in the next few months is to air all his dirty linens, and get it out of the way. I'm glad that Fox News has already done the "he went to a madrassa! His middle name is Hussein!" thing. Yes, Obama was raised Muslim, and then converted to a particularly lefty Black Power Christianity. What's more American than that? But, no, I don't think Obama can stand up to the kind of plain lies that those cheating rightists are willing to spread. Or, rather, I don't think anyone can, and Obama hasn't yet shown himself an exception. But Clinton can: she's been in the national limelight for fifteen years, and every election they throw dirt at her, and every time she comes out even stronger.
I wonder who the veeps will be. Richardson would make a great Vice President — he was, after all, on the shortlists for both Gore and Kerry — but neither Obama nor Clinton can ask him (the latter makes the ticket too centrist-Clintonian, with the former the media will never get over a black guy and an hispanic). And Richardson is too conservative for my tastes. The ticket I'm fascinated by is Obama-Clark. Clinton could ask Obama; I desperately want Obama to be President four or eight years from now, when he's had a little more Senate time — I want him to have chaired a committee; being VP, or even VP candidate, will help him on that road. Obama should not ask Clinton, and she should say no, because she's too ambitious? Maybe, if they in fact get along really well, it would work. But I doubt it.
Besides, if she doesn't win the White House, Clinton should seriously consider party leadership in the Senate. I've never been that enamored of Harry Reid, although he's fine, and Pat Murry, Richard Durbin, and Chuck Shumer are also all kinda boring. So, to complete the fantasy: Giuliani (and a reasonably liberal VP) in the White House, and Pelosi and Clinton controlling the two houses of Congress.
RealClearPolitics reports that, at present, Giuliani wins the GOP nomination (he's at 28% nationally; McCain is next at 20%; McCain, though, wins Iowa and New Hampshire, and Intrade is leaning towards McCain). The Democrats have fewer top contenders, and Clinton flies by with 35%, although the most recent Rasmussen poll has Obama almost tying. Gore is currently leading Edwards.
These polls are of "likely voters", and ask questions close to "if the election were help today, for whom would you vote". The more fun, and even less useful, polls are the head-to-head races, asking those polled to pick which of a particular Democrat and a particular Republican. In those, Obama currently edges by Giuliani, who squeezes past Clinton, who barely wins against McCain. Edwards does the best of leading candidates; Romney does the worst. (This is interesting: OnTheIssues has Edwards the most liberal of all of them, and Clinton and Obama exactly tied.)
I'm actually really excited about Giuliani winning the Republican nomination. He's pro-choice, and supports civil unions; he would pull the party to the left. I'm ecstatic about the idea of having two pro-choice parties in this country.
Of course, that likely means he wins the White House. This I'm not entirely unhappy with: if we lose Congress, then any Republican President would be disastrous, but provided we keep the legislative branch, we'd be able to work with Giuliani. He would not veto our social agenda, and we'd work with him on the economy — hell, Pelosi managed to work out trade bills and budgets with the current President, and these days Demorats are more fiscally conservative than Republicans. I think the country works well when we have different parties in power, and a Giuliani presidency would be a staunch repudiation of the Basest of Republicans.
Then again, perhaps he doesn't win. If spun correctly, this is still a critique of the ultra-right: the rightists nominated him, and couldn't even make good. But their spin machines are better than ours, and I worry that Giuliani losing looks more like a failure to energize the Base — it almost strengthens the ultra-right.
I still think that Clinton, of all the candidates in either party, would make the best President. She's brilliant, and extremely experienced in so many things. But will she surmount her negatives? Thirty percent of Americans right now say that they will never vote for her under any circumstances. Put her alone in a room with her and she'll win them over, of coruse — look at what she's done to Newt Gingrich and other Congressional rightists who used to abhor her. But that's not how elections are won.
Then again, I wonder if she might be the only Democrat who actually stands a chance. Her campaign machine is intense; the NYTimes reports that her husband will, come Fall, start doing campaign stops for her, and for now is bringing in over $100,000 a night fundraising. He plans to win, for her, Arkansas, Kentucky, Louisiana, and Florida.
More than that, Clinton is the only person whom I believe could withstand a Swift Boat attack. The best thing for Obama in the next few months is to air all his dirty linens, and get it out of the way. I'm glad that Fox News has already done the "he went to a madrassa! His middle name is Hussein!" thing. Yes, Obama was raised Muslim, and then converted to a particularly lefty Black Power Christianity. What's more American than that? But, no, I don't think Obama can stand up to the kind of plain lies that those cheating rightists are willing to spread. Or, rather, I don't think anyone can, and Obama hasn't yet shown himself an exception. But Clinton can: she's been in the national limelight for fifteen years, and every election they throw dirt at her, and every time she comes out even stronger.
I wonder who the veeps will be. Richardson would make a great Vice President — he was, after all, on the shortlists for both Gore and Kerry — but neither Obama nor Clinton can ask him (the latter makes the ticket too centrist-Clintonian, with the former the media will never get over a black guy and an hispanic). And Richardson is too conservative for my tastes. The ticket I'm fascinated by is Obama-Clark. Clinton could ask Obama; I desperately want Obama to be President four or eight years from now, when he's had a little more Senate time — I want him to have chaired a committee; being VP, or even VP candidate, will help him on that road. Obama should not ask Clinton, and she should say no, because she's too ambitious? Maybe, if they in fact get along really well, it would work. But I doubt it.
Besides, if she doesn't win the White House, Clinton should seriously consider party leadership in the Senate. I've never been that enamored of Harry Reid, although he's fine, and Pat Murry, Richard Durbin, and Chuck Shumer are also all kinda boring. So, to complete the fantasy: Giuliani (and a reasonably liberal VP) in the White House, and Pelosi and Clinton controlling the two houses of Congress.
Subscribe to:
Posts (Atom)
