A Random Note on Sorting

The Verb View

In the landmark 1981 film “Sorting out Sorting” from the University of Toronto Computer Systems Research Group, we see computational sorts placed in three categories by the nature of the operation (the verb) they execute to accomplish the sort. These three categories are:

• Insertion sorts
• Exchange sorts
• Selection sorts

Insertion sorts find an out-of-order member, put it in the correct position, and then reorders the remaining members to account for this. When an array is used to store the entries in the list to be sorted, this reordering requires a quantity of operations whose number is proportional to the original size of the list. In computational complexity speak we say that this reordering requires order n operations, abbreviated O(n).

There are three  parts to every sort:

• Traversal
• Comparison
• Movement

If the comparison step requires a fixed constant number of steps but the movement requires O(n) steps, the complexity of the sort will be at least the complexity of the slowest step, O(n) in the case here.

Sorts that require O(n) steps to compare and O(n) steps to move tend to run in O(n²) time. For large lists we don't like this as it creates a practical upper bound on the size of the list we can sort. It should be noted that when we are sorting just a few items, an O(n^2) sort can be just as fast, both in execution and implementation as a linear time sort. But it is always poor form to use an O(n²) sort on a large list, especially since there are so many excellent and free implementations that run faster.

The Noun View

The complexity analysis enumerated in Sorting out Sorting assumed that the elements of the sort were, at some point, stored in an array. For some sorts, this array is converted into a tree.

Let’s go back to the insertion sort for a moment. Consider a reordered element inserted between Array[i] and Array[i+1]. If the index [j]of the reordered element was greater than [i+1], then Array[i+1]…Array[j] elements must each be scooted over until their place in the ordered list can be determined. On average some linear fraction of the list elements will have to be moved, and if we do this n times for each element in the list we are left with a O(n^2) time complexity, a famous example of which is bubblesort.

But now instead of storing our list as an array, lets say that it is stored as a doubly-linked list. Inserting an item can now be done in constant time, because we do not have to scoot all the remaining items down the line. So an insertion step that requires linear time complexity O(n) using an array data type, requires only constant O(c) time complexity in the linked list case.

The astute reader will note that this speedup has not been obtained for free. A doubly-linked list requires that we not only store the item itself, but we must also store the links to the previous and next items. If our business plan involved sorting integers, we have tripled our storage costs by using a doubly-linked list.

The mental exercise that comes from this redux is to consider the cost of traversal, comparison and movement of list entries using the following structures:

• Arrays: See Sorting out Sorting
• Doubly-Linked List: See development above
• Stacks (Last In First Out = LIFO)
• Queues (or Lines, First In First Out = FIFO)
• Bags (non-indexed, non-linked, you reach in and see what you get)
• Trees (many kinds of trees each with their own properties)

This blog came from a question I asked myself this morning, "Does bubblesort on a stack give you the Towers of Hanoi?"

Cool Demonstrations

This site shows a nice comparison of sorting methods including their sonic signature.

This is an aid to feeling and learning what is happening during the sort. It is also handy if you have ADD because 15 sorting methods are compared in just six minutes.

The site sorting-algorithms.com enables a comparison of various methods and does the sort while you watch.

It does the best job of showing the performance of sorting algorithms on pathological cases, like nearly-sorted lists, reversed-lists and lists whose pivots are pathological.  One sorting algorithm that I like, even though it is not optimal is shellsort. If you had to stop the sort midway, the list is very close to being in the correct order. One might imagine this shellsort being best in situations where the number of items was very large, or where there was some real-time deadline in force that prevented finishing the sort.

If you want to move past the basics, MIT open courseware has some excellent lectures on the computer science fundamentals of sorting, including the mathematics of proofs briefly touched above.

Finally consider if we could use computing machinery to sort hazardous waste into its constituent components. Wouldn't that be useful!

Recycling Near Miss with a True Rigging Innovation

Ok, I admit it, I recycle everything. It's nuts, but it's a healthy outlet for my obsessive preoccupation that garbage should all be turned around to make new things, rather than rotting away in a landfill somewhere. The only exception to this rule is, "chicken juice drippings", but I digress.

This is a tale of an obsession gone wrong, one two many trips to the bin. There is even a double entendre in there somewhere.

Since the average attention span is now only 7 seconds I am going to shorten this up. Just the facts, Jack Webb style.

Moore's law must be kept intact. Update computers every couple of years, keep them a couple after that, "just in case".

Store in original box away from sunlight and ants that have mutated to eat plastic.

Mac 8500. Not my favorite but there it was in the box, a luxuriously big box with handles and foam liners. It should have its own carrying case.

Recycling a computer here means a trip to Goodwill. The box was placed on the porch.

My wife said, "Someone is going to steal that".

I said, "Let them, it will save a trip to Goodwill."

When I wasn't looking she scooted the big box back in.

Saturday came. It was time to make the trip.

"Just in case", open the box, maybe there are some cables that don't belong to the machine, might need them.

Only there is no computer in the box. Instead a brand new Flexon parachute rig from Rigging Innovations, with my name monogrammed on the left riser, double-wrapped in plastic. It glimmers in the light.

I had never jumped it, but got it to replace my WonderHog.

It almost went to Goodwill.

Now it won't!

I wonder if it still works?

Maybe its time to to find out.

"Morgan": The Gift of This Morning's Home Invasion

I woke up this morning hearing the rumblings of an unknown who had entered into our apartment. No door bell. No ding dong. Struggled for consciousness I heard him going from room to room singing, "Morgan", first softer then louder. "Morgan". Who was Morgan and why was he in my house? Why was this guy looking for him? In MY house! Was a timer ticking off my last seconds? He goes into my daughter's room and I'm still waking up thinking, "What am I going to do?", as he then comes down the hall towards my room singing again, "Morgan". I know the names of the maintenance men, JJ, Reggie, Jason. There is no "Morgan". Before he gets to my door I yell out, "What the #$%^& are you doing in my house?" He said, "I knocked on the door". I bellowed, "Get out". He said, "Okay then" with this weird "It's your loss" tone. Did the door shut? I sleep naked. "What do I do?" I can't go running around the house naked to find "Morgan". Then he actually goes into my daughter's room two doors down singing "Morgan". I feel sick. My daughter's name is not "Morgan and I can't be having that. The three of us just moved into this new apartment complex. It had been plagued by fires. We got a good deal on the rent. "They caught the person starting the fires" we were reassured.

When we moved into this new place my wife put a baseball bat by my bedside window. I'm not a baseball player. It has been sitting unused since the last home invasion. The previous home invader stole my daughter's video camera and jewelry. Then he came into my room and saw me sleeping. I must look like Darth Vader with his helmet off. He fled from the front door leaving it wide open. Maybe it was a woman.

On 9/11 I purchased a 9mm pistol. I don't like guns. After 9/11 I didn't know where things were headed so I figured, "just in case whatever". My dad considered guns after Kennedy was shot, now it was my turn. After the first home invasion I learned something. My gun was locked up under the bed. I was dead asleep. They could have done the Psycho dance on me. What if I had shot them somehow? What if they spurted HIV arterial blood all over the carpet? Carpet is hard to clean, but it is quiet and I don't like the clanging of hardwood floors. Who wants a chalk outline of HIV dead person on the carpet? How do you work that into pleasant conversation? "Oh that's just HIV-dead guy outline, you can step over it...".

After practicing martial arts for years I learned, contradictorily, that I don't like hurting people. Its not the fear of being hurt, its the fear of hurting someone else and all the terrible feelings that come. People are precious. I have this glitch.

I don't like people coming into my house without asking when I don't know what their intentions are. So there is huge conflict between the guilt of inflicting lasting damage and avoiding harm. That is a terrible thing to carry around. There is no Undo command for lasting damage. I have a friend in a wheelchair and I think, "How can we undo his lasting damage?" You can't. Wallerian degeneration. Christopher Reeve had that. Dana died of cancer and a broken heart.


I called the property manager. I called my wife. I called my son who created a Silicon Valley security startup after the first home invasion. Then I got a call from the company that provides apnea supplies. The lady let me vent. The guy was gone. I knew my daughter was okay but I needed to sit down and talk to her. She said a man came into her room singing, "Working". She said, "She didn't like it that a man came into her room while she was sleeping". She said he sprayed something in her bathroom and worried it could make her cat sick.

I was concerned too. Last week a bug man sprayed the apartment with a mist that glimmered and hovered as sunlight streamed through the window. I asked, "What's in that?". The bug man said "Delta Dust".

"Delta Dust". My wife had cancer. Her dad died of cancer. My mom and dad died of cancer. My uncle died of cancer. What is "Delta Dust"?

When I called the property manager she said we were, "scheduled to be sprayed" and that they give out keys to everyone who needs them. I must therefore ASSUME that he was singing "ORKIN" as he went from room to room. "ORKIN".

□

Light Unit Testing and the Barely Bloggable

From the annals of the barely bloggable comes today's adventure, the repair of the light that refused to be repaired. Context: I am a unit testing nut. I have a deeply held and mathematically-decidable aesthetic about testing things before they are assembled and then testing them after they are assembled to make sure that they work, the whole work, and nothing but the work so help me God. This little light of mine, I was going to let it shine. It also magnifies and I was going to let it do that too.

Since this is barely bloggable I will hit the high points.

My desktop magnifier light has been on the blink for some time. By "on the blink" if you haven't gotten the fluorescent "air quotes" pun I mean, it would work, then it wouldn't, then it would, in a decidably undecidable way.

Setting it up after a recent move relegated it permanently to the "then it wouldn't" state, so I set out, for the second time in as many years to drill down and get to the dark root of the problem.

There are three main concerns in such a light of mine:
1) the bulb
2) the starter
3) the ballast

I replaced the bulb, assuming that like me, it had "burned out".

I flicked the switch and then "it wouldn't", or rather, "it didn't".

I took the bulb back to the local hardware store. I thought that the floppy plastic thing that completes the donut bulb held fragile wires. I thought these wires had given up the ghost, meaning, that one of them had broken or could conceivably break during reassembly, replacement or testing.

Much to my surprise the local hardware guy fished out a "flourescent bulb and starter tester" and proceeded to demonstrate that both my bulb and ballast were good. No Home Depot and Lowe's that I have ever frequented has ever hauled out such a tester. This alone saved me two trips to the hardware store, possibly saving my life if I had been killed in traffic on either one, but I digress.

I brought home the now-proven bulb and starter. The hardware guy said and I quote, "If it's not those then its the ballast", refering to the small black autotransformer that parks on the wall outlet.

After reassembly, it didn't, so I disassembled the ballast, un-tape-ing it and spilling out its transformer contents as I had done the during the last spelunking adventure with this light. I proved to myself that the transformer and connections inside were good by measuring the resistance of the one coil at 22 Georg Simon Ohms and confirming that the wiring connected to the blades of the plug by setting the voltmeter to the, "sing to me if its okay" setting, a setting which all VOM users will instantly grok.

So now I have a real problem. My three main concerns, bulb, ballast and starter work.

Enter into the, "take apart things that weren't intended to be taken apart" cave of what-have-we-here.

Buried, and I do mean hidden in the starter base were wires just lying there, never soldered by some worker who had to pee, or go on their lunch break or got a call on their phone. So I soldered the wires and reassembled that which isn't to be broken into and behold, my little light shines. I am going to let it shine before you because it is an excellent example of things not working when they actually should work, because some tiny but critical detail is hiding an assumption on which all illumination hinges. Hallelujah.

Ice Water and ALS

I've seen a lot of people dumping ice water over their heads, but not a lot of people talking about the underlying die off of motor neurons - the hallmark of ALS. Why just motor neurons and not sensory neurons? What is special about outgoing neurons compared to incoming neurons?

According to OMIM - online mendelian inheritance in man. There are ALS tagged genes on chromosomes 1 2 3 6 7 9 10 12 14 15 16 18 20 21 22. That is over 65% of the chromosomes in the human genome.

OMIM

This is bad. It could mean this is a complex, multi-factor disease, like cancer which requires suppressor genes (the brakes) to be turned off and accelerator genes (growth or oncogenes) to be turned on in several places for cancer to emerge. Suppose there is a simpler explanation, say that ALS is a motor-neuron specific auto immune disease, say lupus for motor neurons.  What happens if we make a similar query for lupus?

Lupus is on everything!

Then the genes we're seeing just code for motor neuron proteins that are attacked in this auto immune circumstance. The question that we must always ask is, what advantage did ALS confer on its bearers in the evolutionary sense? For example sickle cell anemia confers on its 1 hit bearers (heterozygotes) resistance to the worldwide killer of malaria at the cost of seriously harming its 2 hit bearers (homozygotes). Survival at any cost... It's very important not to confuse a single factor single-point mutation disease like sickle cell with a complex disease like ALS.

What if we ask the question, what chromosomes have BOTH ALS and lupus marked players? Anding the two charts just give us the first one since lupus is everywhere.

Lou Gehrig was a champion baseball player. This means he had very quick reflexes and effective motor execution relative to the population of competitors. Why would a better motor nervous system confer on one a greater likelihood of auto immunity, or a Huntington's chorea-like duplication error? Huntington's looks different, it is a CG repeat disease on the tip of chromosome 4. These repeats cause errors in vital brain proteins sentencing the sufferers to progressive dementia and eventually death.


Maybe there is a clue in the Zeitgeist having to do with cold water. Will cold water protect the motor neurons? Is there a temperature-sensitive component to the mechanism of this disease?

The Four Costs of System Conversion

I wanted to write a short addenda to my last note on System Administration Principles.

In that first part I introduced:

Principle 1:  The Repair or Replace Decision

Principle 2: The Cost of Additional Computers

Principle 3: The Cloud Advantage

Principle 4: The Dual Platform, Dual Browser Safety Net

Principle 5: Legacy Code

Principle 6: Redundant Systems

Principle 7: Backups and Archives

Principle 8: Monetizing Content

Principle 9: High Value vs. Low Value Content

Principle 10: The Make vs. Buy Decision

With these principles in hand, and a good dose of common sense, I want to broach the important topic of System Conversion.

System Conversion: A change in method or process of accomplishing work or doing business.

Examples of this are changing: 

• operating systems - e.g. Windows vs. MacOS
• internet service providers - e.g. ATT vs. Cricket
• communications providers - Comcast vs DirectTV
• changing email programs - Outlook v.s gmail
• hardware platforms - Dell vs. Apple
• search platforms - Google vs. Bing

More specifically let's say you are unhappy with your email service provider - I myself  want to change service providers, but there is a time and monetary cost to doing so. When I use the word cost, I am referring to  time, space, and money (energy).

It is essential to calculate the cost for two possible scenarios:

1) The cost of continuing to do things as you currently do them.

2) The cost of doing the same thing a different way.

There is an additional cost:

3) The cost of doing the conversion itself.

To make matters worse, there is a fourth, hidden cost.

4) The cost of maintaining two systems while you transition from the pre-conversion system to the post-conversion system.

Doing something a different way does not mean doing it a new way - but it should always mean doing it a better way.

If you calculate these costs, before you perform a system conversion, you are more likely to make a good decision.

Consider the cost of an email system conversion. I am unhappy with Outlook.com because it takes a full thirty minutes to receive a new email message. When I am "cooking" I operate on a considerably shorter time frame than 30 minutes. Even 30 seconds when I am thinking about something can seem like an unproductive eternity.

I used to run Outlook 20XX on Windows YY on my PC ZZ. Then I migrated to Outlook.com as support for Windows was beginning to wane. Now I am almost completely transitioned to Outlook.com and my email is horribly slow. To examine what my options are I visited emailclientmarketshare.com. At this writing the marketshare is this:

I have an archive of 52,000+ emails reaching a back to 1996. So storage space is an issue, as are stability, longevity and ease of converting yet again.

My wife taught me a shopping trick. When she sees a set of similar products in an aisle and one of the products is nearly sold out, she buys THAT product. It is sort of a reddit, "wisdom-of-the-hive" approach. But that trick won't work here because there are more considerations than just the client.

After counting my costs the lowest cost is for me to continue what I am doing and letting Outlook 20XX coexist with Outlook.com. But I am simultaneously transitioning to the MacBook Pro as a backup platform which gives me portability. After as season it may become much easier to perform the email System Conversion.

Mixed Signals

Radio, digital or analog, is all about mixed signals. There is a popular saying, "I'm getting mixed signals", which implies confusion. But in radio, mixing is everything. Without it we cannot send or receive audio signals over radio frequency connections that use space itself as the connecting "wire".

Audio signals can be electronic, meaning they are represented by electrical signals flowing in wires. They can also be mechanical as in solids, liquid or air when we hear a sound or make a sound by tapping the table. My wife is tapping the table right now because she wants to go somewhere, but I'm hoping to finish this before she leaves me. Anyway:

Radio signals can also be represented by electrical signals flowing in a wire, or by photons of long wave light shining through the air and transiting the atmosphere, the ionosphere and ultimately empty space.

To make any kind of a useful radio we have to combine an audio signal - or a digital signal, as in where are my internet packets - anyway I was saying, we have to combine an audio frequency signal with a radio frequency signal prior to sending it out on the airwaves. Exactly the opposite occurs in the receiver:

goo.gl/09wN6m

To conclude this preamble, make the following mental note: When we mix one audio signal (the drums) with another audio signal (the guitar) on a mixing console in a recording studio, we are ADDING the signals together.

When we mix an audio signal with a radio signal in a radio prior to transmitting them, we are MULTIPLYING the signals together. This is called MODULATION. It comes in various flavors, AM, FM, PSK, but in all of these, the signals get multiplied to get on the air. When the signals encounter a receiver they are DEMODULATED, also by MULTIPLYING them with a radio frequency signal.

Mixers in Recording Studios Add Their Inputs

Now here's the bizarre and very cool thing that makes radio possible. When you mix two audio signals by adding them, the resulting signal is just the sum of the original signals, drums and guitar or what have you. Run with it. But when you mix two radio frequency signals by multiplying them the result is TWO signals. 

Here comes the good part. The product of two signals is two new signals - one at the sum of the original frequencies and one at the difference. So its like you can't get away from the sum thing. Multiplying them produces a sum (and  a difference which is just adding the negative). These sum and difference frequencies are called intermediate frequencies - IF for short - and they can be filtered and demodulated to discover the original signal be it audio, be it drums or guitar, or even my missing internet packets.

Since I am very interested in radio I was curious when mixing two signals what the issues were with regard to amplitude, frequency and phase.

Primarily I was concerned with the following. When we are receiving very faint radio signals from distant places like quasars or galaxies we have a very faint signal that is being mixed with a very powerful frequency produced by a local oscillator that enables us to move the sum or difference frequency to an intermediate frequency where we can grab it for demodulation (AM, FM, PSK or other). The whole mixing and unmixing thing is separate from the demodulation thing. We just have to agree before modulating what the demodulation scheme will be, so we don't even have to talk about that for this concern.

Long story short, I threw a couple of signals into my favorite geometric analysis program - Geometry Expressions™ - GX for short - written by the gang at Saltire Software - an AMAZING shop. Anyway here is what I found. Let's say the red signal is the local oscillator that you are tuning the signal in with. It can be as powerful as you want since you have control of it. Let's say the green signal (for little green men) is the signal that you are trying to pick out of the cosmic dust, litter, flotsam and jetsam. The blue signal is the mix of the two, and for this example we can see that it has about the same amplitude  as the little green men signal. 

From noise considerations, we don't want our red local oscillator to be any "louder" than the green signal, because we don't want any noise that may be in the oscillator to swamp out our fragile tiny signal in green.

From this we posit that the magnitude or strength or amplitude (however you want to say it) of the mixed signals is on the order of the strength of the LESSER of the two signal magnitudes. So if you want to pull in galaxy X, you better amplify it before you mix it, because its signal is only going to emerge from the mix as strong as it went in. The trouble with amplifying it before you mix it is that you amplify the noise too and one would like to avoid that. So you have to filter the INCOMING signal to only be in a band where you think useful information will be. This can be done starting with the antenna, if you know what frequency your information is going to be found on. This works fine for 89.1 FM because you know where the information will be. Bad for Galaxy X and the little green men.

One other thing if both signals are the same frequency (idealized case) and they differ by nothing but the phase of the signal (where in the clock cycle we started), then we get a DC offset in the resulting signal. This is usually blocked by a filter capacitor. It is an issue that must be addressed. Here is how it looks in GX:

Note that the signal strength in this case is half the strength of either signal. Making the case that when looking for little green men, its best to be as quiet as possible...

Ten Computer System Administration Principles

The Device Boom

With the explosion of tablets, smart phones, apps, fitness monitors, remote controls and personal computers, we have been thrust into being computer system administrators.

Breathe

Making matters worse the tools we use to manage these devices has not kept pace with their population explosion. Some vendors, who will go unnamed, have made matters worse by stripping out features for Home users that ease routine administrative tasks like backing up irreplaceable information, updating operating systems and migrating files. You know - email, photographs, documents, financial records, blog entries, homework and so forth.

A careful reading of these ten administrative principles can lead to new places. They can be combined to make new derived principles. Some are similar, but just different enough to warrant their own mention For others you can substitute the word "house", "car", "pet" or even "relationship" to derive additional benefit.

Principle 1:  The Repair or Replace Decision

After concerted good faith effort to fix a broken "computer", if the "computer" does not respond, then it should be replaced without mercy.

Principle 2: The Cost of Additional Computers

For each additional computer system that you maintain, your time is diluted by the total number of computers. So if you have two computers that you often use, you must spend twice as much time maintaining them. Three computers will require three times as much time to maintain. If you have five airplanes you can spend all your time and money maintaining them and none of your time getting to fly them.

Since time is money, this also pertains to computers you pay someone else to maintain.

This principle gives us one obvious thing and one surprising thing.

The obvious is that we want the fewest possible machines possible, that get the job done.

The surprising thing is that if we already have 10 computers, adding an additional one doesn't cost very much. This leads to server farms and the economies of scale.

But I am assuming you don't want to run your own server farm. This leads us to ...

Principle 3: The Cloud Advantage

It is more economical to use a computer in the Cloud, provided it is secure, than it is to maintain your own server. Every second your own server runs, the more of your time and money it saps as it becomes obsolete. I use Dropbox (DB) for this purpose. I can access everything I do from ANY computer ANYWHERE I am located. The first 5 GB is free and they charge after that. DB runs the server farm. DB does the backups. DB fixes the broken equipment. DB is the transparent utility.

Principle 4: The Dual Platform, Dual Browser Safety Net

After losing support on various platforms through the years I have learned:

Any software you buy or use should run efficiently on more than one platform, currently chosen from the set {PC, Mac, Linux}. Any web-borne software you buy or use should run in more than one browser, currently chosen from the set {Chrome, Firefox, Safari, IE}. The food chain alphas flip every decade or so, no matter who was on top to start with.

Principle 5: Legacy Code: If you have legacy code you have to keep the legacy computer running in both hardware and software. The same thing applies to code that is not dual platform or dual browser.

Principle 6: Redundant Systems: When running an important system, it is valuable to have an IDENTICAL hot backup waiting in the wings in case the primary system fails. Note that this principle balances the cost of additional computer principles like porridge and the three bears. By which I mean, 1 critical system is too few, 3 is too many, and 2 is usually just right. In fault-tolerant systems that have "votes", you want odd numbers of machines so you can take the best 2 of 3, the best 3 of 5 and so forth. This gets into RAID disk arrays and error-correcting memory schemes, so that fault tolerance can live at the subsystem level, at the box level, or both.

Principle 7: Backups and Archives:

Always have at least one and preferably two copies of any document in addition to the original. The copies should be on a different physical drive, and preferably in a different physical location. This can get unwieldy, see principles 1, 2 and 3 for guidance.

If you backup a file that has a virus, the virus will be in the backup.

Principle 8: Monetizing Content:

Any content, software, or data, that you are "spinning" on an available drive should produce value for someone. If it is never accessed or used, there is no use paying to spin it. It should move to archival storage which is a HUGE but separate issue.

Principle 9: High Value vs. Low Value Content:

If you have authored specific content, that content is of high value. If you did not author that content and someone else is spinning it, then you don't have to. Its value is lower because it is reachable elsewhere. If there is high demand for the content then you need a redundant system or mirror.

Principle 10: Make vs. Buy Decision:

Don't make something when you can buy that thing for less money and time than it would cost you to make it. You should also consider the cost of the environmental impact of the life cycle of the thing when tally your cost.

(Disclaimer: this content is offered without warranty of merchantability or fitness for any purpose, expressed or implied, which really should have been its own principle!)

Anding on the Backend

We use Boolean operations everyday without thinking about it.

Whenever we read, write, say or decide using the terms "and", "or", or "not" we have used a Boolean operation.Whenever we think about selection, inclusion, exclusion or negation, we have used a Boolean operation.When programming computers (stay with me for second) we often write phrases like:

if (conditionA is true) AND (conditionB is true) then do something.

When making routine decisions we might think something like:

IF (sky is blue) AND (temperature is warm) THEN go outside.

We can talk about what the terms sky and blue and temperature and warm mean later.

Not only can we write symbolic expressions, or think symbolic thoughts, we can draw symbolic pictures.

Where I am going is this. 

When we write or think in the way discussed above, we are doing our Boolean operations on the front end.

that is, "IF such and such (Boolean operation) THEN do something"

But we can also perform Boolean operations in our actions on the backend.

That is to say, "IF such and such then do something (Boolean operation)".

For example

IF (sky is dark) THEN (take umbrella) AND (go outside)

We can even have Boolean operations on the front and backend

IF (sky is dark) AND (temperature is cold) THEN (take umbrella) AND (wear coat) AND (go outside).

But forget all this for a moment. I said all that just to say the following. If we are doing an OR instead of an AND we run into a problem.

Whenever we ANDed two or more actions, it is understood that we did BOTH or ALL of them, whether sequentially or concurrently it doesn't matter right now. But when we OR two or more actions we are left with a curious nondeterminism:

IF (sky is dark) OR (temperature is cold) THEN (take umbrella) OR (wear coat) AND (go outside).

We are left with an unspecified decision. These decisions come up all the time in real life, and we often dismiss them, but they are an enormous source of decision noise in our lives.

I would like to dig in to both the mechanistic/automatonic view of this nondeterminism, and also the practical and real world view of it.

That's the deal!

Ode to an Orchestra Obscured

The concert is a time to stop and think, third row center C. My muse, my mizzen mast, cracks the rust off from above.

The conductor is drinking stratospheric air; a shining breath of freshness from Olympus and the rest.

I would write this ode for him alone - a focal point for sure, but my problem runs much deeper.  I am in love with an entire orchestra, whose story I yearn to know. Each player a dedicated life of practice and disposition, each a bag of presents, tricks and tips.

The conductor is of agile build, a shock of hair, and sweeping gestures demanding unseen witnesses to rise up and pay attention. A genius, I will give him that, not worn upon the sleeve or spoken to a mirror. It is in the light of piercing eyes, one as called then chosen. Enough of that. I’m glad for a wooden bar to brace a treacherous fall from grace. His wooden bar, it blocks my view, accepted for its safety, lest rising  up upon his toes he steps back into the void.

Last night’s concert - I could write about them all. But one must choose a single instrument. I choose wind and brass and key and string!

As for strings, the blackened box was full, sitting grandly in the foreground, performing surgery on my open heart. A keyboard surgeon, a pair of hands, an arc in smooth curved motion with ebb and flow, easing up and down. There, a note, a stroboscopic sleight of hand. Each one, an evening out, a beginning, middle and an end.

Yet even in perfection there was a problem, that not pianist,  nor conductor, nor orchestra could stand. The problem was the piano that I looked upon - like one would look up to a mountain knowing there was nothing I could do.

It was in freefall overhead, dropped from a skyscraper after being lugged up endless stairs. Descending like an anvil, whistling in freefall, as I walked unknowingly on the sidewalk of ailse C, carrying flowers to honor one musician, then another, and then finally them all. Not knowing that in a fleeting moment, I would hear that sound.

Gazing upward I got to know the belly of that piano like a prisoner doing time. Marking off the days, I could see the milking of its pedals, not the twinkling of its strings, not its long wrapped copper notes, nor its trebles strung in threes. I could not consider the infamy of its even-tempered tuning, the low notes flat, the high notes sharp - let the fretless understand.

By this massive ruse in ivory my orchestral view was blocked, choked from light, a plant on the jungle floor doomed by rules I did not make to die in desolation. You ask, "What was it pray tell you wanted to see?" Deep breath. It was the bridge, the bow, whether near or far, whether dinner or dessert, a salad or a feast. The scoot, the slide, the brawn, the bangs, the beard, the chin, the pad. The chrome, the brass, the wood, the grain, the warp, the weft the weave. The letters, the luthier, the make, the model. The hope, the skill, the miss!

But I could see! A constellation of creatures, each with six legs! The back legs sets of four, then slats of wood then two thick ones dark with wider feet, some fronts were striped forms. Four were always still and thin, two were always moving. Nourishment perhaps?

I vote for fewer legs, but alas I have no vote. I can only offer a petition. Strike that. I am a creator of the most demanding kind! Foisting tyranny on the innocent on long-furled scrolls, untied at a moment's notice! No prisoners of war, no hostages begging for mercy, just an ode to an orchestra obscured.

What I Learned from Bill the Buddhist

Whatever the endeavor:

"If you practice, you will improve"
"People get bored"
"People are impulsive"
"People think half thoughts"

A guy is going 90 MPH in his car.
He opens the door and says, "I'm going to jump out".
He thinks a half thought.
He doesn't think about what will happen when he jumps.
-----
I met Bill the Buddhist while walking around the Forest Heights track. I was melancholy and decided to start a conversation to distract myself.

I pointed out that the track, open to the public all year round,
was surrounded by barbed wire - an interesting contradiction.

Then I observed, "Isn't it interesting how people who don't know each other never walk or drive side by side. One will speed up, the other slows down. They space themselves apart as far as possible."

Bill the Buddhist then told me a blue-haired woman pulled up  beside a friend of his in her car. "Like Marge Simpson" I said. "Yes", he replied going on, "She looked at his friend in his car, looked at her door and promptly, assertively, locked her doors. His friend then looked down at his door and pushed HIS lock down, locking his own doors." We agreed this was funny.

Bill had more stories such as "Feral children". "If you don't get to them by the time they are seven, they never socialize." I thought rescuing feral children was an interesting and under discussed topic.

He talked about "same substance", that people are all the same, male, female, old, young, etc. "All flesh" he said. I said, "Yes, but if the flesh is the body, they have different drivers."

He talked about social norms and people and how people are affected by the norms of other people. When people are isolated they become feral again and will do strange things.

He talked about how he went to live in Japan for a year and a half. He said, "You don't really learn a culture in that time,
but it opens your eyes on your own culture." I asked him, "How so?". He said something profound but I forgot it.

Then he talked about how they drive on the "wrong" side of the street in Japan. "Like in Britain" I asked? "Yes" he replied.
He thought it profound that they chose left and we chose right.
I did not. I thought it was arbitrary and insignificant and said so.

Then we started talking about bifurcations.
Bifurcations are where a choice has to be made and 
one culture chooses one way, and another chooses the other way.
Like which side of the road to drive on, which affects
on which side the steering wheel is. Bifurcations are everywhere.
Your liver is on the right, but it could have just as well been on the left, and so on.

We talked about language bifurcations.
How Egypt had a language based on pictures and we had one based on the sound of words. Picture languages are great for nouns and bad for verbs. We talked about the Babylonians, the Rosetta Stone, the Indo-Europeans and things that could have gone either way and did, or did not.

Then we started talking about communication. I told him, "Communication is symmetric if A can talk to B and B to A."
Before that we talked about Godel and undecidability and how Godel starved himself to death when his wife left and couldn't fix him dinner.

Before that he said the inner part of a person is infinite.
I told him, "I don't feel infinite on the inside, I keep bumping up against the stops."

Then I mentioned that communication is reflexive if you can talk to yourself. We mixed this in with perception, which is a kind of self-talk. He lamented the incompleteness of communication and mentioned Iran as an example. I said communication is very complete if you do it properly.

Then we made up a game. A bifurcation game.
Each of us writes down one of two symbols, and gives it to the other person. The other person then writes down their symbol and gives it to the other...
The person is not obligated to read the symbol they received before they transmit their symbol. This special case is called "Not listening".

Then Bill the Buddhist said these are his principles:

Whatever the endeavor:
"If you practice, you will improve"
"People get bored"
"People are impulsive"
"People think half thoughts"
A guy is going 90 MPH in his car.
He opens the door and says, "I'm going to jump out".
He thinks a half thought.
He doesn't think about what will happen when he jumps.


-----
I met Bill the Buddhist while walking around the Forest Heights track. I was melancholy and decided to start a conversation to distract myself...

Circuits As Proofs: Episode 1

Electronic Circuits As Mathematical Proofs
Episode 1: Resistance is Futile

L. Van Warren MS CS, AE

Warren Design Vision
 wdv.com

Friday, February 3, 2012

Introduction

I want you to forget for a moment that you are reading this as a consequence of digital technology.  I want you to forget that the screen it was written on was imaged as ones and zeros running through a multitude of logic gates at high speed. I want you to forget the mountain of computational complexity we use everyday as our lofty perch.

A Lofty Perch

The Naked Truth

At various points in school and life you may have encountered a mathematical proof. For many they are tedious, boring and purposeless arguments that seem to serve no purpose but their own. I hope to convince you that without them, the digital revolution you now enjoy would not have happened. Further, I hope to give you a way of seeing proofs as never before, as everyday objects,  familiar as bread and butter that you can consume to increase your understanding.

An Everyday Yet Monumental Example

When one enters a dark room, a common behavior is to flip on a light. A switch is thrown, and usually, but not always, the light turns on. Most of the time we proceed without giving this monumental event a second thought. But I tell you, that when and if that light came on, at that very moment, you proved something. You proved something mathematical. You proved something real. You proved that the light, and everything connected to it," worked". This is profound.

Not finished with your monumental act, you did something just as stupendous. When you left the room, the switch was thrown again. Usually, but not always, the light turned off.

If you flipped the switch AND the light came on, you proved that:

1)    the switch "worked", it served as a human control between an OFF state and an ON state.

2)    the wires from the switch to the light were connected and conducted electricity.

3)    the light itself "worked", that its filament, tube, or junction converted electricity into light & heat.

4)    that the power company, however complex, was intact and functioning.

If you flipped the switch and the light didn't turn on, you proved that one or more of the above statements was false, an equally majestic and complex treat of logical possibility.

Possible Explanations

It is possible, if you flipped the light switch, that something else happened.

It could be, that at the moment your hand touched the switch, you were abducted by magic aliens who connected your mind to an illusion machine that made you believe that the light turned on or off.

A Futile Resistance

This explanation violates common sense. It seems highly improbable. For Kurtnestetic incompleteness, we will consider such explanations unlikely at our current scale and existence. The magic aliens will be left in the care of our more mechanical readers, quantumly speaking

Situation as Circuit

Using this free download we sketch a circuit that represents our situation:

We have already committed several acts of abstraction, having:

·       replaced real world objects by symbols in a graph

·       chosen a voltage source  to represent the power company

·       chosen an LED to represent the light "bulb"

·       sized the components so they didn't blow up

The resistor is along for the ride. It represents inefficiency and injustice in the system,  such as "wires aren't perfect conductors" and poverty. We could have a separate resistor for each of the three original wires, but each time we add a resistor we must add a wire. This tendency of things to become more complex before they get simpler is called, "intermediate expression swell". Just how bloated things get is an interesting problem we will sidestep for now.  Pushing all three resistors through the circuit and placing them side by side allows us to replace them all by a single resistor. All the losses are then treated as single equivalent loss, adding another act of abstraction to our efforts!

In doing so we invoked the rule:

"Resistors in Series Add Linearly"

R_equivalent = R₁ + R₂ … + R_N

Having transformed our little world into an "equivalent" circuit, we must define what "working" means. "Working" means Proven, Demonstrated, QED.  We define "working" to mean that current is flowing around the loop in sufficient quantity and with sufficient potential to turn on the light. This is something we can measure in both worlds, simulated and real. We can measure voltage, we can measure current and we can measure whether the light is on or off. The single measurement of whether the light is on, abstracts away the need for two measurements, voltage and current. Aside: I always measure the voltage of household batteries before and after installation. It is incredibly informative. Measurement of current requires a meter alias ammeter to be placed in series with other circuit elements. Current flow is measured in units of Coulombs per second, or Amperes, much as water flow is measured in liters per second. It is represented by an arrow, labeled here "Meter de Courant" in a twisted French homage to the German American mathematician Richard Courant.

When the Hardware meets the Footwear

Two pictures conclude the example. One picture with the switch OFF, one with the switch ON. QED

OFF:

ON:

The astute reader will notice that the current is actually flowing more voluminously in one direction than the other. This happens too fast for us to see, so we think that the light is on, when it is actually pulsating. Because the light is an LED, it only shines when conducting current in the forward arrow direction. The back-flow happens because real diodes are naughty. They leak. Current flow is taken as positive when traveling from positive pole to negative pole of the source. The squiggly "current-limiting" resistor is sized to keep the LED from burning up like a comet and destroying our pretty little world in one puff of smoke, also known as the smoke test of a proof. The tiny fence on the arrow of the diode implies that current is not supposed to flow backwards even though it does. The act of proof, the light turning on when the switch is thrown, isn't affected by these details. They do however suggest deeper and more interesting issues are afoot.

Acknowledgements

This work is dedicated to parents, professors and friends that inspired it.
Illustrations are linked to their respective sources.

© 2012 · Warren Design Vision