Table saws are fearsome machines. Crosscutting is when you cut across the grain: this is what you think of when cutting a 2x4 in half: you get 2 shorter 2x4s. Rip cutting is when you turn a 2x4 into a pair of 2x2s. Resawing is when you turn a 2x4 into two 1x4s. Guess which one's scariest. Now guess which one I wanted to do yesterday.

The bandsaw is the usual choice for resawing, but as the Sheriff said, "we ain't got a bandsaw."

So how do you hold a 1" thick piece of wood on edge so the blade can slice it through the middle? You use a nifty shop-built vacuum fence:

Basically it's just a plywood box with holes in one end and a port for the shop vac on the back. It holds on *great*: it takes a solid tug to pull the plank off the surface. Slipping backwards happens more easily, but rather than drilling bigger holes, I just stick a nail in the rightmost hole to give the wood a little lip to ride against.

I didn't have a hole saw the right size for the vac hose, so I put a lid over the port and use velcro to stick the hose to the lid.

Also note how I made the box: rather than fiddling with the edges of the box to make the faces perfectly parallel, I cut some 1" strips for the edges but then used the 3/4" edge for the side rather than the 1" face. Since the plywood has very consistent thickness, the box came out very true.

The holes on the backside were an attempt to make the fence stick to the rip fence, but putting a flat base turned out to be much more stable, and also gave me room for a handle. That makes it easy to hold down and against the rip fence while moving it forward. Remember to take small 1" bites at a time, and to keep the same face against the fence if you have to flip the piece over (when the plank is taller than the height of the blade). It's also good to clamp a piece of scrap above the plank: that prevents the plank from lifting up, and covers most of the extra holes. It also tends to hold the offcut in place after I cut all the way through. I'm not entirely comfortable with that, so maybe I'll start clamping the scrap slightly above the workpiece to give the offcut room to float free.

Dimensions: Vacuum box: 14" x 9" x 3 thicknesses of 3/4" plywood. 1/8" holes spaced at 1" intervals. The 14" length and flat base let me use it with my crosscut sled for even better control.

Oh, it's also very important, after building the box but before installing the base, to put the small holes face down on a flat floor and hook the vac hose to the output port. Hovercraft!

## Monday, November 19, 2007

## Thursday, August 23, 2007

### Solving the halting problem

The halting problem has always bugged me. Recap: assume someone wrote a function halt(f) that returns true if f halts, and false if f runs forever. We write a function f that says:

f():

..if(halt(f)) then run forever

..else halt

That is, see what halt thinks we're going to do. Then do the opposite, forcing halt to be wrong about what we're going to do. Since we can contradict halt(), it must not be possible to write a halt() that's always right.

That always seemed to me like cheating: ask the fortune teller what word you're going to say next, then say something else.

Today I asked myself what I'd do if I had to answer whether a given function halts. I'd do the following:

halt(f):

..if we're being called by a program trying to make a liar of halt(), then:

....print("This program tries to make a liar of halt. I will lie to the program to ensure it halts.")

....return false

..else if f calls halt() and contradicts its output, then:

....print("Note: this program tries to contradict halt(), but that's okay because I always lie to such programs to ensure they halt.")

....print("Program halts.")

....return true

..else if f just plain halts, then:

....print("Program halts.")

....return true

..else:

....print("Program runs forever.")

....return false

Then if we call halt(f), we get:

Note: this program tries to contradict halt(), but that's okay because I always lie to such programs to ensure they halt.

Program halts.

But if we call f(), we get:

This program tries to make a liar of halt. I will lie to the program to ensure it halts.

halt() then returns false to f(), and f() indeed does halt as predicted. In each case, halt() provides me the most useful answer to the question at hand, and is always correct in a certain sense. That is, it does lie to f(), but it does it on purpose and lets you know that.

So, I've made a social argument about a useful definition for halt(). But I did have to give halt() a supernatural power to make it work, at least as far as normal functions are concerned. halt() has to be able to examine not only the function passed to it, but the function that *calls* it, in order to operate correctly. That is, halt() behaves differently when we simply called halt(f) than when we called halt(f) *from within f() itself*! Same call, different calling context, and that makes all the difference.

Of course, that's not allowed for proper functions: the rules say that your function's universe has to contain only itself and its arguments. So proper functions have no way of knowing that the function calling them is trying to make a liar out of them.

So here's a slightly less informative but altogether more conventional kind of function:

halt(f):

..if f tries to contradict the output of halt() then return -1

..if f halts then return 1

..if f runs forever then return 0

This one breaks the problem of "halting" into three pieces instead of two: programs either halt, run forever, or are smartasses that try to take advantage of halt(). The question then becomes how many functions fall into the "smartass" category, not whether there exists a function that can tell you how arbitrary programs behave. If it turns out that lots of interesting functions actually have that smartass nature by "accident" as it were (that is, that the "smartass" property is intrinsic to something important they're trying to tell us about the world but can't because they fall into the middle category), then I might actually be inclined to agree that the question of halting is a great mystery of the universe. But that seems doubtful to me, and I don't know of any functions of that sort.

So I guess what I'm saying is that sure, halting taken as a dichotomy is uncomputable in the rigorous mathematical sense, but that doesn't tell us anything at all useful about how hard it is to tell whether programs actually halt, because the answer isn't a dichotomy. (And also because halting is actually solvable for finite machines, but that's another rant).

Okay, so now having written that, I had to scratch my head: have I actually said anything new or interesting here? Well, it's almost certainly not new, but I think there are common perceptions that are totally wrong. Take this example from CS theory class slides, italics added:

Link to slides.

I claim that the first and last italicized statements are wrong. The second statement is interesting, but I'd have to ponder some more. (I italicized it because it might point to something interesting about the "smartass" class of problems.)

f():

..if(halt(f)) then run forever

..else halt

That is, see what halt thinks we're going to do. Then do the opposite, forcing halt to be wrong about what we're going to do. Since we can contradict halt(), it must not be possible to write a halt() that's always right.

That always seemed to me like cheating: ask the fortune teller what word you're going to say next, then say something else.

Today I asked myself what I'd do if I had to answer whether a given function halts. I'd do the following:

halt(f):

..if we're being called by a program trying to make a liar of halt(), then:

....print("This program tries to make a liar of halt. I will lie to the program to ensure it halts.")

....return false

..else if f calls halt() and contradicts its output, then:

....print("Note: this program tries to contradict halt(), but that's okay because I always lie to such programs to ensure they halt.")

....print("Program halts.")

....return true

..else if f just plain halts, then:

....print("Program halts.")

....return true

..else:

....print("Program runs forever.")

....return false

Then if we call halt(f), we get:

Note: this program tries to contradict halt(), but that's okay because I always lie to such programs to ensure they halt.

Program halts.

But if we call f(), we get:

This program tries to make a liar of halt. I will lie to the program to ensure it halts.

halt() then returns false to f(), and f() indeed does halt as predicted. In each case, halt() provides me the most useful answer to the question at hand, and is always correct in a certain sense. That is, it does lie to f(), but it does it on purpose and lets you know that.

So, I've made a social argument about a useful definition for halt(). But I did have to give halt() a supernatural power to make it work, at least as far as normal functions are concerned. halt() has to be able to examine not only the function passed to it, but the function that *calls* it, in order to operate correctly. That is, halt() behaves differently when we simply called halt(f) than when we called halt(f) *from within f() itself*! Same call, different calling context, and that makes all the difference.

Of course, that's not allowed for proper functions: the rules say that your function's universe has to contain only itself and its arguments. So proper functions have no way of knowing that the function calling them is trying to make a liar out of them.

So here's a slightly less informative but altogether more conventional kind of function:

halt(f):

..if f tries to contradict the output of halt() then return -1

..if f halts then return 1

..if f runs forever then return 0

This one breaks the problem of "halting" into three pieces instead of two: programs either halt, run forever, or are smartasses that try to take advantage of halt(). The question then becomes how many functions fall into the "smartass" category, not whether there exists a function that can tell you how arbitrary programs behave. If it turns out that lots of interesting functions actually have that smartass nature by "accident" as it were (that is, that the "smartass" property is intrinsic to something important they're trying to tell us about the world but can't because they fall into the middle category), then I might actually be inclined to agree that the question of halting is a great mystery of the universe. But that seems doubtful to me, and I don't know of any functions of that sort.

So I guess what I'm saying is that sure, halting taken as a dichotomy is uncomputable in the rigorous mathematical sense, but that doesn't tell us anything at all useful about how hard it is to tell whether programs actually halt, because the answer isn't a dichotomy. (And also because halting is actually solvable for finite machines, but that's another rant).

Okay, so now having written that, I had to scratch my head: have I actually said anything new or interesting here? Well, it's almost certainly not new, but I think there are common perceptions that are totally wrong. Take this example from CS theory class slides, italics added:

Link to slides.

"Why should we care that HP is undecidable?

It’s not that people have tried for centuries to solve the Halting Problem and are now deeply disappointed to discover that no algorithm exists.

It is that we now know that decision problems exist that are unsolvable.

*There are things we can imagine wanting to do, but which cannot be done by following an algorithm.*

Equivalently, we now know there are recursively enumerable languages that are not recursive.

*For such languages, we have no parsing algorithm that will terminate on all inputs.*

Are there no practical applications of HP?*Sometimes, programs loop. So you may want to design a compiler that warns the programmer if asked to compile a program that will loop.The undecidability of HP tells you that unless you limit the range of programs in some way, you will not be able to design such a compiler.*"

I claim that the first and last italicized statements are wrong. The second statement is interesting, but I'd have to ponder some more. (I italicized it because it might point to something interesting about the "smartass" class of problems.)

Subscribe to:
Posts (Atom)