Follow up: Economies of AI

Yesterday, I gave a talk about my earlier post Economies of AI with supplemental material to illustrate the point (slides in Chinese). One addendum in my talk is that I referenced a book by George Polya, How to Solve It (1945), to illustrate the comparative strengths of AI and humans when it comes to problem solving.

Polya broke down problem solving in four phases:

• Definition: what are the unknowns, how to collect data, what are the conditional limitations, can we derive the unknown from the limitations, and are there any logical gaps or contradictions?
• Planning: are there known solutions, similar solutions, ways to break down the problem (by divide and conquer), can we solve a specialized problem and then generalize?
• Execution: step by step, verify the correctness of each step.
• Assessment: are the steps reasonable, are the results reasonable, other ways to solve the problem, applications of the solution to similar problems?

I argued that these principles of problem solving universally applies to any problem, but humans are uniquely qualified for problem definition and result assessment. The reason is that the motivation to solve a problem comes from humans, as AI does not have its own motivation nor intent. And as the beneficiary of the problem solving, only humans can judge whether the outcome works as intended, as AI has no means to gather real-world feedback. On the other hand, AI either excels or will excel at planning and execution.

It may be surprising, or completely unsurprising depending on your perspective, that humans are so good at correcting mistakes because being wrong actually hurts physiologically. AI lacks this neurological feedback.

I also made a quadrant to illustrate the division of labor based on value proposition and risk.

	Low Risk	High Risk
High Value	🧑 🤖  🏭?	🧑  🤖   🏭?
Low Value	🧑  🤖 🏭	🧑   🤖  🏭

In summary, humans should focus on work that has high value, AI should avoid work with high risk, and automation (deterministic algorithm) is typically relegated to low cost work (even though low cost does not necessarily mean low value).

In retrospect, I should have added another dimension to compare volume / value to show that anything high value could still justify building automation even if the volume is low. The infographics is helpful to summarize the ideas, but some nuances are lost.

Early in my talk, I also made the analogy of economies of scale using mobile phones as an example. At first, only a selected few can afford car phones, then more elites could afford cellphones but they are still bulky. Mobile phones became more prevalent and affordable with the indestructible Nokia 3310 even though functionality is still limited, and now everyone has a smartphone. I argue that AI right now is analogous to the Nokia 3310.

Audience questions

Q: Although humans should focus on high value work, what would happen to those who could not find high value work?

Economists know about the Pareto distribution which states that 20% of the causes achieve 80% of the outcome. You can see this in teams or group projects where a few people deliver most of the value. You also see this in nature where 40% of worker ants are idle, but these idle ants serve as reserve capacity. IT uses redundancy as backup strategy by following the 3-2-1 rule with 3 copies of data, on 2 different media types, and 1 stored offsite. These are examples showing that reserve capacity or redundancy is needed in any resilient systems.

Without the reserve capacity, the system will collapse under stress such as war or disasters.

Q: With AI or automation taking away low value work, how would a person develop the skills to perform high value work?

Instead of focusing on the planning and execution, education should instead focus on the design and assessment aspects of problem solving, the first and final phases according to Polya.

I also wrote an article earlier My advice if you are a 13 year old vibe coding to become the next Bill Gates espousing the ideas of building up vocabulary and validating outcome as the essential skills to have.

Q: In your economies of scale analogy, AI is currently like the Nokia phone. What would it take to become a smartphone?

Currently, users spend a lot of effort on prompt engineering (the problem definition phase of Polya) because the prompt has to be precise and without ambiguity to avoid AI slop (see I Tried to Kill Vibe Coding). AI could evolve to fill some of these definition gaps by making heuristic guesses about what the prompt might mean when a problem is stated. This can happen in the assessment phase whether any solved problems are relevant to the problem at hand. On the other hand, the assessment of the efficacy of the outcome can still only be done by the user.

Economies of AI

This is a cost-benefit analysis on using AI to solve problems and comparing how it fares with classical methods, e.g. deterministic algorithms or manual labor, and the cost of the creation of automation.

A fair warning: currently, LLM is not able to summarize this article correctly because of my unique perspective (example), as this article is not about the H-word at all. You should try to read it yourself. If you are impatient, at least read the first sentence of each paragraph and the conclusion.

AI vs. Deterministic Algorithms

An example of a deterministic algorithm is to compute an arithmetic expression like "1+2+4". There are well-known and efficient ways to compute it.

• First the string is tokenized: "1+2+4" → ['1', '+', '2', '+', '4']. This is called lexing.
• Then the string is organized into an abstract syntax tree: ['1', '+', '2', '+', '4'] → Plus(1, Plus(2, 4)). This is called parsing.
• Then the abstract syntax tree can be traversed recursively and the value is computed: Plus(1, Plus(2, 4)) → Plus(1, 6) → 7. This is called evaluation.
• Under the hood, a machine would compute the addition using logic gates called an Adder.

For AI to do the same, the tokenizing is similarly done by a deterministic algorithm, but the rest of it is done through many large matrix multiplications. The size of these matrices are much larger than the length of the input tokens, and matrix multiplications take \(\omega(n^2)\) time complexity. Logic gates for a Binary Multiplier is also much more complex than an Adder. Large matrices take up more memory space and more communication bandwidth to move the data.

Which is why a machine could make billions if not trillions of calculations a second, but it would take AI a few seconds to complete a single prompt. Not to mention the power consumption needed by AI is several orders of magnitudes greater than a deterministic algorithm.

This is why for the problems for which we have a deterministic algorithm, it would not make economic sense to use AI to solve these problems. Furthermore, it would be AI's best interest to offload any such prompts to a deterministic algorithm. AGI may be an academic interest, but it is not economically viable for doing mundane tasks. Just like we would not be hiring humans to crunch numbers anymore once computers became commonplace.

AI vs. Manual Labor for Doing the Work

To achieve economic parity, AI would have to be relegated to the odd jobs—the long tail for which no deterministic algorithm exists. For these odd jobs, a person should try to do it first before trying AI. This is for two reasons: once they have done the job themselves, they have a better understanding how to write the prompt; and they will be in a better position to evaluate whether AI is doing the job correctly. Skipping this step is a common reason for getting AI slop. It is not necessarily the fault of the model when the prompt itself is sloppy.

If an odd job is truly one-off, it may make sense to do it only manually because the cost of learning by doing is comparable to the cost to understand how to write the correct prompt. When doing things manually, we gain insight about any potential problem, and then adjust the assumptions, requirements or expectations to avoid these problems. AI is unlikely to challenge the assumptions made by the prompt unless specifically asked. We wouldn't know what to ask for unless we are already aware of the problems. We wouldn't be aware of the problems unless we tried to do it ourselves. So just do it first. When the job happens again, then offload it to AI. This weird trick of DIY-ism will save you tons of time writing prompts, perhaps counter-intuitively.

AI vs. Manual Labor for the Creation of Automation

When these odd jobs become frequent, it then makes sense to invest in the time to automate them by creating a deterministic algorithm and writing programs. Traditionally, a human would write the computer programs for these algorithms. AI could presumably write them now, but I argue that the economy impact difference is minimal between the two. The reason is that whatever the cost is to develop software, the cost is amortized over the many jobs it ends up automating. Even though the one-time development cost may be expensive, it becomes negligible if you spread the cost over many jobs. AI may be 10x more productive than humans for writing programs, but 10% of negligible is still negligible.

What is not negligible is the cost of poorly designed automation, which has a multiplicative effect on the defects of the outcome. The defects can be the incorrectness of the output, or the inefficiency in the algorithm itself usurping too much resources or taking too long. If the algorithm is poorly designed, then it would screw up over many jobs, and the expense to clean up the mess is the polar opposite of negligible: it would be astronomical. It doesn't matter whether the algorithm is designed by a human or AI.

When it comes to the creation of automation, use whatever tool at our disposal to design an algorithm that reliably achieves the correct outcome and can do it efficiently. Even if AI is not able to vibe code a project from start to finish, it can still be a valuable tool for humans to learn about the nature of the problem through prototyping.

Divide and Conquer

So far, we treat the problem as a monolith. In reality, a problem can be broken down to many subproblems. It is like when computing "1+2+4" we compute one addition at a time, either:

• Leftist: (1+2)+4 = 3+4 = 7
• Rightist: 1+(2+4) = 1+6 = 7

And there is more than one way to break down the subproblems. The ability to decompose problems also gives rise to efficient algorithms known as divide and conquer algorithms, and in many cases it can be proven that this is the optimal way to solve a given class of problems.

When discussing AI's economic proposition, we should remember that many bespoke problems can be reduced to subproblems that are recurrent and can be solved at a greater economy of scale than if we considered each problem in isolation.

For example, car builders would design common parts, e.g. the engine and chassis, that can be reused across multiple models of sedans and SUVs. These engines and chassis are built out of common parts like standardized screws, nuts and bolts. Greater economy of scale is achieved by using common off the shelf parts, even if the end product is bespoke.

In the same way, we can mix AI, deterministic algorithms, and even manual labor in different configurations to achieve economy of scale.

Value Proposition

Another issue we neglected is the value proposition of the outcome of the work. In the pre-computer ages, human calculators were used for extremely high value work even though they are slow and error prone, from artillery in a battle that increases the probability of winning the battle, to scientific calculations that raced to create atomic weapons that ended World War II. Or they are employed for the backbone of economy itself, such as finances and accounting.

When computation became so cheap, they are used for entertainment like video games or watching cat videos.

Similarly, the method for which we use to solve a problem—manual, AI, or automation—speaks nothing about the value of the work that employs them. When it comes to high value work where the stake of failure is high, AI will still face a fierce competition with automation and human ingenuity, in part because of AI's high error rate. On the other hand, when AI is used to generate videos for entertainment, who cares if the video shows someone with seven fingers, or if the text is malformed, provided the entertainment value is good? There is no stake in these failures.

When company management makes the decision to replace work with AI, it is a signal that they consider the value proposition of the work to be low. They could be proven wrong by the market or the competition. Indeed, competition is a remedy for Enshittification, and we need Anti-Trust enforcement to ensure competition. I'm not sure if labor protection helps, since it enables complacency, not ingenuity.

Conclusion

We reach a conclusion where the economic viability is unsurprisingly dictated by the economy of scale.

• High volume work should be done by a deterministic algorithm, not AI.
• Low volume work could be done by AI, but humans should do it first so they can understand the problem better, for writing better prompts and for evaluating the efficacy of the output.
• One-off work should be done by humans first to understand the problem.

When deciding which problems are high volume, low volume, or one-off, we should use a divide and conquer approach and break bespoke problems down to reusable and recurring subproblems, so we can achieve greater economy of scale. Again, this should not be a surprise for economists. If anything, computer science just provides the vocabulary to explain why the economy of scale is achievable.

We also came to a conclusion that AI slop is enabled by enshittification, and the remedy is more competition through Anti-Trust enforcement; this is also unsurprising for economists.

The more sober minded person will come to realize that AI is just one more way to get things done, and it is still subject to the same market forces as everything else. Commodified work will eventually be replaced by deterministic algorithms, not AI. High value work will still face competition from human ingenuity, unless the human chooses to be complacent or if our values somehow become corrupt.

That last point that our values have somehow become corrupt is my greatest fear.

My advice if you are a 13 year old vibe coding to become the next Bill Gates...

(Insert obligatory AI generated Ghibli styled graphics here.)

If you are a 13 year old vibe coding to become the next Bill Gates, here are the computer science concepts you will need to know to successfully direct AI to do the right things. I assume you want to build the next big thing and not just fixated about the 70's BASIC interpreter that Bill Gates wrote when he was 20 without AI. Also, if you want to go into fundamental research on AI or quantum computing, vibe coding is probably not what you're after, but it can be helpful to learn about randomized algorithms.

If you ask AI today the same question, you would have gotten some hand-wavy advices, and here are my takes on why they are not that useful.

• Master prompt engineering.
• Why this is not useful: the only way you master prompting is by having the right vocabulary for the fundamental concepts in computing, and you need to understand the concepts behind these vocabularies. It is not effective to prompt with an alphabet soup of jargons unless you use them in a meaningful way.
• Learn the tech stack (e.g. Gemini, GitHub Copilot).
• Why this is not useful: tech companies are going to make AI as easy to use as tap water. Obviously, there is fascinating practical engineering about water resourcing and plumbing infrastructure to get the water to your tap, but it's not exactly rocket science to learn how to turn on the faucet. Anyone who thinks they have a particular edge in prompt engineering will find out that it is quickly disappearing.
• Problem solving and strategic vision.
• Why this is not useful: don't just dream about things in your head. It is even more important to learn to try things and observe the outcome. If something didn't happen as expected, try to understand why. This is not something AI can do for you, since AI can only learn from its training data. Always validate your ideas in the real world and pivot as necessary.
• Financial literacy.
• If you pay attention in high school math class, you should have the tools you need to predict the outcome of your decisions. Watch this video about why Math Just Got Important.

Instead of recommending specific framework or product (since you can ask AI for more timely recommendations), here is a bucket list of timeless computer science concepts that you will want to learn:

• Computer architecture, especially about the memory hierarchy and principle of locality in the context of cloud services. Separation of code and data, which is important for security.
• Why is it important: memory hierarchy and principle of locality lets you understand how all computer systems operate under the same space-time constraints, similar to relativity in Physics, and the cost-benefit trade-offs needed to optimize it (e.g. caching).
• Without the discipline to separate code and data, mixing the two is a constant source of exploits compromising cybersecurity at national levels.
• Algorithms and data structures: when you learn about sorting, set your sight on the time and space complexity analysis and try to not get bogged down with the mechanism itself. Hash table is going to be relevant in load balancing, and Graph traversal for network architecture.
• Learn programming in the context of algorithms and data structures so you have a vocabulary to describe them.
• Why is it important: complexity analysis tells you why your system is provably not scalable when the dataset becomes larger, not even if you add more computing resources to it.
• Network architecture: DNS, IP addressing, client/server and load balancing.
• Why is it important: although many "cloud" providers have this abstracted away, understanding the network architecture lets you design your cloud in a more cost effective way and be able to debug when issues arise.
• Server side: HTTP and REST, cryptography (TLS, JOSE), SQL (particularly about SQL injection which is what happens when you fail to separate code and data).
• Why is it important: although many frameworks also abstract away most of these details, your system architecture is limited by the assumptions made by the underlying protocols. Ultimately this boils down to trade-offs, whether to accept these limitations as "good enough" for your application or seek alternatives, e.g. HTTP long polling vs. WebSocket, X.509 vs. JWK, SQL vs. NoSQL.
• Client side: fundamentally, at least HTML/DOM, CSS, and Javascript.
• They are very capable nowadays, so you don't really need a separate framework, but feel free to let AI try different frameworks.
• Why is it important: you still need to know HTML, CSS and Javascript in order to debug framework code.

There are some more advanced topics that could be relevant for domain specific work like games, especially the triple A titles with good graphics and physics, unless you are satisfied writing yet another unimpressive Minesweeper.

• Linear algebra for computer graphics and physics modeling.
• More advanced data structures and algorithms like quad tree / octree, path finding.
• Audio and video: digital signal processing, Fourier analysis.
• Information theory: data compression, error correcting codes.

In a world where the cost of answers is dropping to zero, the value of the question becomes everything. It is still important to learn the concepts so you have a vocabulary to express ideas in your head, and to observe if your ideas work in the real-world and pivot if not.

AI, The Theranos of Software Engineering

Breaking news! Vibe coding achieved the utterly impressive feat! Macintosh System 7 Ported To X86 With LLM Help. The original System7 ran on Motorola 68K. The author claimed that they ported the OS to x86 in 3 days, with a fully functional Finder and GUI, and no access to the original source code. The project files can be found on GitHub.

It is understood that the port ran under QEMU to simplify dealing with real hardware, which has to do many things like ACPI power management. But as you may have surmised from the title, this is not the only "shortcut" that has been taken.

ISO contains just the kernel?

To start, let's take a look at how to run the project from the instructions provided:

# Build the kernel
make

# Create bootable ISO
make iso

# Clean build artifacts
make clean

# Run in QEMU
qemu-system-i386 -cdrom system71.iso -serial stdio -display sdl -vga std -m 256M

So let's take a look at the Makefile to see how the ISO was built.

ISO_DIR = iso
KERNEL = kernel.elf
ISO = system71.iso
GRUB = grub-mkrescue

# ISO target
iso: $(ISO)

$(ISO): $(KERNEL)
	@echo "Creating bootable ISO..."
	@cp $(KERNEL) $(ISO_DIR)/boot/
	@echo 'menuentry "System 7.1 Portable" {' > $(ISO_DIR)/boot/grub/grub.cfg
	@echo '    multiboot2 /boot/$(KERNEL)' >> $(ISO_DIR)/boot/grub/grub.cfg
	@echo '    boot' >> $(ISO_DIR)/boot/grub/grub.cfg
	@echo '}' >> $(ISO_DIR)/boot/grub/grub.cfg
	@$(GRUB) -o $(ISO) $(ISO_DIR)

The ISO is made using grub-mkrescue. The kernel is linked using the multiboot2 specification, which means grub would have switched the x86 CPU into 32-bit protected mode with a flat address space.

But it is a little surprising that the ISO comprised of just the kernel.elf and grub.cfg, devoid of all other assets such as fonts, icons, application binaries. There is no filesystem because everything is compiled into the kernel.

Indeed, you can find the hard coded icons and the hard coded font bitmap. The FontResources is really some code to download fonts from the Internet using curl, but this is not compiled into the kernel, and this is not the code used to generate the hard coded font bitmap either. This is probably just dead code.

If there is no filesystem, then it is a wonder why the project contains HFS filesystem code?

Dead Code Galore

There is a huge amount of dead code in the repo, all generated AI slop. This is an impressive catalog: AppleEventManager, ControlManager, ControlPanels, DeskManager, DeviceManager, DialogManager, EventManager, FS (HFS), FileMgr, Finder, FontManager, FontResources, GestaltManager, ListManager, MemoryMgr, MenuManager, PatternMgr, Platform, ProcessMgr, QuickDraw, ResourceMgr, Resources, ScrapManager, SoundManager, TextEdit, WindowManager.

I have spot checked a few: The FS code has mentions of btree and catalog, but it is an in-memory filesystem (no actual disk volume support). The QuickDraw code does not contain any shape drawing code, i.e. the code purporting to draw the line or oval does not actually render the pixels. There is no implementation of the Bresenham's algorithm.

Only a handful of these managers are referenced in main.c, and even so, only the initialization function is called. There is no evidence that main.c actually uses any of the managers in any substantial way. For example, even though it includes the QuickDraw header, most of the drawing routine is in main.c itself.

What's in a main?

So what does the main.c actually do?

• Writing to the serial console using outb.
• The serial port input is used to simulate GUI interaction, e.g. 'm' activates the menu, 'a' activates the Apple menu.
• Draws console text in VGA mode.
• Multiboot2 handover.
• Drawing of text, apple logo, window, rectangle, and icon.
• Fake initialization of managers.
• There is some mouse handling using hard-coded coordinates to map cursor to UI elements. But this is commented out.

In summary, we just get a very thin veneer of what is minimally required to draw some UI in QEMU and using serial port to interact with it.

Conclusion

This is perhaps not the most flattering case study of using LLM to vibe code. AI faithfully created a bunch of dead code, but what was actually working is a small amount of code that is minimally required to create the appearance of a working operating system.

This whole thing reminds me of Theranos. Its CEO, Elizabeth Holmes, charmed her investors into believing that she invented a miracle medical diagnostics machine that purported to be able to run a bunch of tests using only a single drop of blood. In the few demos they did, they actually drew vials of blood using the normal process and ran the regular lab tests behind the scenes. The machine never worked.

It took Theranos (timeline) from rising to fame in 2015 to fraud indictment in 2018. ChatGPT was first publicly released in 2022. How many more years will people discover that AI is fraud? Probably never, unless somehow AI starts to put people's lives in danger, but not out of malice, just incompetence.

Infinite Monkey Theorem, Debunked

If you let a monkey hit random keys on a typewriter for an infinite amount of time, will it happen to write the complete works of Shakespeare? Common wisdom says that not only will it write Shakespeare, but it will “almost surely” type every possible text an infinite number of times.

The proof idea goes like this: the probability to produce a permutation matching the complete works of Shakespeare is very small, but still greater than zero, so it will “almost surely” happen.

This is assuming that the monkey will eventually produce such permutation with a non-zero probability.

What if some permutations are simply not possible? There could be several reasons why this particular monkey and this particular typewriter could not have written Shakespeare. In order of increasing complexity:

• Some letters on the keyboard are broken, so some letters in the works of Shakespeare could not be typed.
• Due to the clumsiness of the monkey, it is only able to hit the space bar before or after hitting the letters above it. This means that every word has to always begin and end with ‘z’, ‘x’, ‘c’, ‘v’, ‘b’ ‘n’, or ‘m’. Shakespeare often used words that do not satisfy this criteria, so the works of Shakespeare could not have been written.
• The monkey is not able to repeat what it types within a certain number of words, so phrases like “to be or not to be” can never be written.

Infinity does not mean that it will allow every permutation. An example is the infinite sequence that concatenates the set of numbers consisting of only even digits: 0 2 4 6 8 20 22 24 26 28 40 42 44 46 48 etc. This sequence is infinite, but it would never contain the number ‘1’.

(On the other hand, the sequence of all even numbers concatenated will contain all finite numbers, including the odd numbers; since starting from 10—which is still an even number—we simply ignore the last digit and look at the tens and above, e.g. 123 is contained in 1230 1232 1234...)

This is not an argument about “almost surely” being practically zero. Instead, we are simply saying that infinite monkey is not almost surely, as the output is handicapped in some way albeit still infinite.

If we want to apply the infinite monkey theorem elsewhere, infinity alone is not sufficient. We have to also show that the desired permutation has a non-zero probability to happen, as this is not a given. On the contrary, an application that only establishes infinity can be disproven by showing that the desired output actually has a zero probability of happening.

∞ ⨉ 𝜀 = ∞ but ∞ ⨉ 0 = 0

In reality, we often confuse the mechanism of the permutation with the existence of output. We cannot say that the complete works of Shakespeare exists in the output implies that it must have been produced by the monkey. What if we have a programmed typewriter such that, if the monkey hits ‘s’ a million times in a row, would insert the complete works of Shakespeare? The complete works “exists” in the output, but it is not produced through the monkey's mechanism of permutation.

(This is analogous to the panspermia hypothesis saying that life could have been introduced from an external source rather than permuted naturally within the system. The hypothesis allows that a system capable of sustaining finite life may not have been able to produce life infinitely.)

Showing that some improbable event has zero probability of being produced could be quite difficult but “almost surely” doable. However, if we try to categorically argue that “almost surely” is practically zero, then the argument is only “almost surely” believable.

Deep Learning and Solving NP-Complete Problems

This recent article about AlphaGeometry being able to solve Olympiad geometry proof problems brings to my attention that there have been active research in recent years to combine deep learning with theorem proving. The novelty of AlphaGeometry is that it specializes in constructing geometry proofs, using synthetic training data guided by the theorem prover, which previous approaches have had difficulty with.

As a formal method like type checking of programming languages, theorem proving tries to overcome the ambiguity of mathematical proofs written in a natural language by formalizing proof terms using an algebraic language with rigorous semantics (e.g. Lean), so that proofs written in the language can be verified algorithmically for correctness. In the past, proofs had to be tediously written by humans, as computers had great difficulty constructing the proofs. Computers can do exhaustive proof search, but the search space blows up exponentially on the number of terms, which renders the exhaustive search intractable. However, once the proof is constructed, verification is quick. Problems that are exponentially intractable to solve but easy to verify are called NP-complete.

Traditional proof searching limits the search space to simple deductions, which can offload some tedium from manually writing the proofs. In recent years, machine learning is used to prune or prioritize the search space, making it possible to write longer proofs and solve larger problems. It is now possible for computers to construct complete mathematical proofs for a selected number of high school level math. The idea is a natural extension to what AlphaGo does to prune the game's search space, which I have written about before.

This is quite promising for a programming language that embeds theorem proving in its type system to express more elaborate safety properties, such as Applied Type System (ATS) designed by my advisor, which I have written about before. Programs written in ATS enjoy a high degree of safety: think of it as a super-charged Rust, even though ATS predates it. Now that generative AI can help people write Rust, a logical next step would be to create a generative AI for ATS.

I would be interested to see how machine learning can be applied to solve other NP-complete problems in general, such as bin-packing, job shop scheduling, or the traveling salesman problem. However, machine learning will face fierce competition here, as these problems are traditionally solved using approximation algorithms, which comes up with a close-enough solution using fast heuristics. Also, only a few of them have real-world applications. Admittedly, none are as eye catching as "AI is able to solve math problems" giving the impression of achieving general intelligence; in reality, the general intelligence is built into the theorem proving engine when it is used in conjunction with machine learning.

However, I think proof construction is a very prolific direction that machine learning is heading. Traditionally, machine learning models are a black box: even though it can "do stuff," it could not rationalize how to do it, let alone teaching a human or sharing the same insight with a different machine learning model. With proof construction, at least the proofs are human readable and have a universal meaning, which means we can actually learn something from the new insights gained by machine learning. It is still not general intelligence, and the symbolic insight to be gained might very well be a mere probabilistic coincidence, but it does allow machine learning to begin contributing to human knowledge.

Self-Driving Car Challenges

Mercedes recently announced level 3 self-driving that takes legal liability. Typically, the levels of autonomy are defined by situations where the car is able to operate without human intervention, but being able to assume legal liability is a huge step forward. Levels of autonomy would only remain a marketing slogan unless it can be tested in court. The cost of liability will be factored into the insurance premium, so self-driving only becomes economically viable if the insurance premium can be lower than that of a human driver.

However, Mercedes' legal responsibility comes with limits: on certain (already-mapped) highways, below 40 mph, during daytime, in reasonably clear weather, without overhead obstructions.

The first challenge that any camera based system must overcome is the stability of the footage. You can see from this test that a car mounted camera with improper image stabilization (circa 2016) would produce a wobbly and shaky image. The wobble can be counteracted by shortening exposure time (high camera shutter speed) but this requires good lighting condition, hence the reasonably clear weather requirement. Furthermore, when the car is traveling fast, you need a telephoto lens to look further ahead for hazardous conditions, but longer telephoto also exacerbates the wobble, hence the operating speed limit of the self-driving. If the video footage is bad, it won't help much if you feed this into machine learning because "garbage in, garbage out." More recent cameras such as a GoPro has improved image stabilization (circa 2021) that also works on a toy car (circa 2020) which is more challenging to stabilize. These cameras can produce clean image under more forgiving lighting conditions.

Car manufacturers who are serious about their self-driving should be licensing camera stabilization technology from the likes of GoPro.

Self-driving cars using LIDAR face a different challenge. LIDAR works by sending a short pulse of light and observe reflections, so it is not dependent on external lighting conditions. But when there are multiple LIDAR equipped cars on the road, they could be picking up each other's signals which might seem like noises. As such, a LIDAR has to encode its own unique ID into the light pulse and filter out any pulse not coming from itself.

A third challenge is about how to legally dispute a claim in court. A self-driving system must be able to produce a rationale why it made any given decision, and the decision has to be legally justifiable. Previously, machine learning is a black box that could produce surprising results (it recognized a dumbbell only because it has an arm attached to it), but explainable AI is making some progress. Similarly, self-driving technology must be explainable.

Explainable self-driving technology can be thought of as a driving instructor that happens to be a computer. The driving instructor not only has to make the right decision on the road, but it also has to explain to a student why it is the right decision given the circumstance.

Car manufacturers that want to assume legal responsibility should aim for a computerized driving instructor instead.

A musician would understand that in order to perform at 100%, they must practice up to 120%. This mindset applies to a lot of engineering problems where safety is at stake. Building structures such as elevators are often designed with load considerations at ~200% rated capacity or more (ASCE/SEI 7-10 1.4.1.1 (b)). When it comes to self-driving, the specs are less quantifiable, but the design qualifications must similarly exceed expectation in order for the technology to be viable.

Revival of Harvard Architecture for the Mitigation of Ransomware Attacks

Pictured below is the Gropius House in Lincoln, Massachusetts, which was the former residence designed and built by the renowned architect of the Bauhaus movement and emeritus chair of the Department of Architecture at Harvard Graduate School of Design, Walter Gropius.

But the Harvard architecture revival I'm writing about is not that kind of architecture. It was a computer machine architecture in the punched tape era that separated program and data in two different pathways. The Harvard Mark I machine was designed by Howard Aiken at Harvard University. He took inspirations from the Analytical Engine mechanical computer designed by Charles Babbage, who was the mathematics mentor of Ada Lovelace, the first computer programmer and the daughter of poet Lord Byron.

There is poetic justice about the fact that computer programming came out of the conjunction of mathematics and poetry.

What makes Harvard architecture computers notably different from today's computer is that programs were read-only, and data could not be executed as programs. In today's computer, programs and data are stored on the same storage medium. Anyone who can put data on a computer can also run it as a program.

Security breaches happen in two steps: (1) someone has write access to a data path, and (2) subsequently leverages the data path to upload and execute unauthorized programs on a computer they do not own. Gaining write access for step (1) is not that hard. Many computer systems that handle data actively solicit data from non-privileged users. Step (2) relies on having some knowledge of vulnerabilities in a running program that can trick it into passing control flow onto arbitrary data.

Case in point is WordPress, which is a blogging platform notorious for having vulnerabilities that result in security breaches. That's partly because it is built on PHP, a language that makes it easy to run data as program:

• Once file upload is enabled on a site, PHP will allow it for any script on that site even if that particular script never expects file upload.
• A moderately complex site breaks down their code into several files, and the first file include() or require() other files to bootstrap the program's functions. The file to be included is a computed path that could be any file on the filesystem.
• PHP can be configured to limit the path of what could be included using open_basedir. This limits exfiltration of system files that are not part of the public site such as /etc/passwd, but uploaded files are often moved under open_basedir which can then be included.
• Any file type could be included, even if it is an image file with PHP code embedded in it.

The user only needs to upload a malicious image to WordPress and trick it to run the image. It's less of an issue for a private WordPress installation, but on a shared blogging site like wordpress.com where anyone could register an account, anyone can cause a security breach and steal other people's passwords. That's why people shouldn't reuse passwords on multiple sites.

Once they hijack the computer, they also hijack whatever data was entrusted to be handled on that computer. They may also modify existing legitimate programs on the computer and hide illicit code there, which makes it very costly to discover and clean up after a security incident. This is how ransomware works in a nutshell. Some crooks turned security breaches into a profiteering criminal enterprise.

If today's computers have separate program and data pathways, security breaches would only be limited to the original unauthorized data path access but would not escalate to become a complete hijack of the computer.

Modern computers provide some facilities to separate code and data, but they are optional and must be deployed judiciously in a production environment in order to be effective.

• Executable space protection designates parts of the memory only for handling data and prohibits executing it as code. This protects programs that are already running from remote code injection vulnerabilities.
• Enforce writable data to be non-executable (i.e. W^X). This is typically part of the executable space protection for running programs, but the same principle can be applied to programs and data stored on disk.
• Copy on write is a storage policy that maintains snapshots of data modifications. This can make it easier to restore the filesystem to a former state before the security breach.
• Some operating systems support making a filesystem read-only, e.g. read-only bind mounts.
• Some filesystems have the option to make files non-executable on a volume, e.g. zfs exec=off, noexec mount option.
• Code signing verifies that a program comes from a trusted party and has not been modified in an unauthorized manner. Verification and execution must happen atomically. Otherwise an attacker has an opportunity to modify the program between verification and execution to evade detection.

They all work towards the same principle as Harvard architecture, where program is read-only, and writable data cannot be executed as program.

Ultimately, the reason why programs must be read-only has to do with accountability requirements imposed by Sarbanes-Oxley Act in response to corporate scandals such as Enron. Programs running in production must be able to establish its provenance, and that someone has reviewed and certified that the program serves its intended purpose. If the program is writable after the certification, then that would put its provenance in doubt.

In a sense, if a company falls victim to ransomware attack, there must be a loophole in the accountability of its information systems. Revival of Harvard architecture would close the loophole and eliminate ransomware attacks.

How Computability Could Help Understand Procrastination

The weather has been fine this summer for any sane-minded person to sit at home writing blogs, but today it's clear that summer has come to an end. I brewed myself a cup of coffee this morning to sulk at the rainy mist outside of my window while reading an article about how Apple is bad at design since 2013, which sent me spiral-minded to reminisce an anecdote about a boss asking me to do something to which I said is technically infeasible, and he bemoaned "you scare me when you say that." It reminded me of the introduction in Computers and Intractability book by Garey and Johnson where this poor chap has to defend himself to his boss why he can't find a tractable algorithm for a problem.

In computer science, an algorithm is intractable when even a modestly sized problem, say a problem that involves analyzing only hundreds of items, would take all the computing power in the universe until the end of time and still won't find an answer. More formally, such algorithm is said to take an exponential time to compute. If you multiply 2 times 2 times 2 and so on for just 90 times, you reach a figure \(2^{90} \approx 10^{27} \) that is bigger than the age of the universe in nanoseconds (roughly in terms of one computing cycle of a computer), and keep multiplying for 300 times, you reach a figure \(2^{300} \approx 10^{90} \) that is bigger than the number of atoms in the universe. So a problem size of 400 would not be solvable even if all the atoms in the universe were to compute until the end of time.

Several strategies were illustrated in the book what this poor chap might say to his boss.

• He could say "I can't find an efficient algorithm. I guess I'm just too dumb." The boss is unimpressed.
• He could also say "I can't find an efficient algorithm because no such algorithm is possible." But it is hard to justify why the algorithm is impossible to the still unimpressed boss.
• Finally, the chap would say "I can't find an efficient algorithm, but neither can all these famous people." Sadly, the boss is still unimpressed.

I think the reason for the boss to be unimpressed throughout is that the cartoonist copied the same drawing of the boss from the previous cartoons, but he's perhaps doing it to make a point. You can't impress a boss if he doesn't get what he wants.

Or the chap could say to his boss, well I know there is an efficient algorithm that will give you a figure that is generally good enough but will be off by a factor of 2 in the worst case. Would you take it? This is known in computer science as an approximation algorithm.

It's not hard for common folks to understand that there are intractable problems in life, and you just have to make do with something that is good enough. You can be a perfectionist, but finding the optimal solution to a problem will keep you busily procrastinating until the end of the universe. To counter this tendency, Steve Jobs famously said "real artists ship!"

One could argue whether Apple's design ills since his passing is due to procrastination, or perhaps they took the anti-procrastination to an extreme and shipped a premature product, but it's clear that Steve Jobs and Tim Cook would take different approaches. Whereas Tim Cook would be unimpressed when his designers tell him the problems are intractable, Steve Jobs would understand what can be reasonably accomplished within a given time frame and plan accordingly.

When solving an intractable problem, one has to plan ahead: it's better to take the complete output of an approximation algorithm than to interrupt an optimal but intractable algorithm and use the incomplete output.

Prediction of the world in 2075

It's one thing for Steve Wozniak to be asked off-guard about his predictions of the world in 2075, during an interview where he was supposed to promote the Silicon Valley Comic Con. I suppose it's not totally far-fetched since some comic books have a futuristic setting. Nonetheless, it's fun for a layperson to wonder about these things.

Predictions grounded on truth tend to be accurate though it may be a question of sooner or later. I think many of Woz's predictions are truth-grounded. Some of my predictions differ because I may have a different perspective of truth. Or because I just have more time to think about them as supposed to answering interview questions on the spot.

When asked whether Apple will be around in 2075, Woz affirmed, making the comparison to IBM founded in 1911. He also later clarified that Apple had the cash to do many restarts. My own prediction is that Apple, Google, and Facebook will be around, but they are likely going to become a conventional company like IBM. Once a company is filled by tenured people who have found their place in the hierarchy, they tend to resist change. The only way to prevent it is to force all employees (including the founders) to retire after 10 years, no exception; if you allow any exception, then institutional squatters will figure out a way to game the system. However, I don't imagine anyone would want to work in a company like that.

Also, conventional companies continue to deliver value, so there is nothing wrong with being conventional. The only folks complaining are the Wall Street investors who reap profit from the disruption but shoulder none of the responsibilities.

Reinventing a conventional company requires incremental steps. There will be disruptions, but the leaders will have to figure out a transition plan to minimize the effects of disruption. It's like refactoring code, then rolling out the software update across many data centers. Tech companies are probably more adapt at treating their people with finesse because they already do that with machines.

Woz predicted that machine intelligence will become ubiquitous in governing everyday lives. I think it is not going to be feasible due to liability issues. Machines already fail a lot. Conventional algorithm failure modes are theoretically predictable even though people don't always anticipate them. Machine intelligence glitches, however, are utterly unpredictable (e.g. there is an odd strategy for beating machine playing Super Mario Smash Bros). It is challenging to figure out exactly what is going on in a neural network, though some introspection techniques are possible through synthesis.

My prediction is that we will end up using machine learning to help us improve conventional algorithms. We will continue to develop introspection techniques into machine learning in order to help us understand how it works, and then put this understanding into developing conventional algorithms instead. I had written previously about how AlphaGo may inspire a new class of Go algorithm based on divide and conquer.

About Mars colony, Woz predicted that Earth will be zoned for residential use and Mars for heavy industry. This is probably inevitable. However, because shipping from Mars to Earth takes 150-300 days, my prediction is that it will be further limited to manufacturing goods that are: (1) inherently toxic to make, (2) do not become obsolete in several years (e.g. no iPhones), and (3) made by companies that can afford a long product cycle where initial investment and profit may be separated by several years. At the moment, it seems like making nuclear reactor fuel on Mars is the only feasible application.

Do you like my predictions? Leave your predictions in the comment below.

Proof of Sum of Exponential Powers

My renewed interest in proof of exponent laws came from reading the Harvard Entrance Exam, 1869, which David Robert Palmer painstakingly typed up. In the exam there were sections of Latin and Greek, History and Geography, are various mathematics. It's fascinating that the words in Latin and Greek are already provided, so knowing how to conjugate is all that is required. The maths section are heavily calculation based. It seems that these sections serve to test only how nimble the minds are in solving known problems, but not so much whether the students exhibit the thought process of solving unknown problems. But one question intrigued me.

Question (3) in the algebra section reads, "What is the reason that when different powers of the same quantity are multiplied together their exponents are added?" It is asking about the exponent law for product of powers, \( a^x a^y = a^{x+y} \). Knowing the prestige of Harvard, giving an informal answer is likely not satisfactory. But most of the so called "proofs" that are prevalent in textbooks essentially boil down to the following reasoning.
\[ \underbrace{a a \dots a }_{x \text{ times}} \cdot \underbrace{a a \dots a}_{y \text{ times}} = \underbrace{a a a a \dots a a }_{x + y \text{ times}} \]
This appeals to the intuitive understanding that \( a^x \) is \(a\) multiplied \(x\) times, so when you multiply the result also by \(a\) for another \(y\) times, you get \( a^{x+y} \). This is hardly satisfying as a proof.

Another "proof" is to reduce this to the additive law of logarithms \( \log{xy} = \log{x} + \log{y} \), but this is like throwing the hot potato to someone else.
\[ \log{a^x a^y} = \log{a^x} + \log{a^y} = x + y \\
a^{\log{a^x a^y}} = a^{x+y} \]
And since \( a^{\log{c}} = c \) i.e. log is the inverse of exponent, so \( a^{\log{a^x a^y}} = a^x a^y = a^{x+y} \).

There are other exponent laws without formal proofs, but for this article I'm going to focus on the sum of powers.

Formal proof

We appeal to proof by induction for the formal proof. First we establish the base case for exponentiation:
\[ a^0 = 1 \]
Also recall that \(1\) is the multiplicative identity, so \( x\cdot 1 = 1\cdot x = x \), and \(0\) is the additive identity, so \( x+0 = 0+x = x \). From this, we can prove the base case where \( y = 0 \), i.e. \( a^x a^0 = a^x \cdot 1 = a^x = a^{x+0} \).

Now for the inductive case, we need both the axiom of exponentiation \( a^x \cdot a = a^{x+1} \) and the induction hypothesis \( a^x a^y = a^{x+y} \). We proceed to show that \( a^x a^{y+1} = a^{x+y+1} \).
\[ a^x (a^{y+1}) \underbrace{=}_{\text{axi.}} a^x (a^y a^1) \underbrace{=}_{\text{assoc.}} (a^x a^y) a^1 \underbrace{=}_{\text{I.H.}} a^{x+y} a^1 \underbrace{=}_{\text{axi.}} a^{(x+y)+1} \]
In the equations above, "axi." means the axiom of exponentiation, "I.H." means application of induction hypothesis, and "assoc." means associativity (which is true of all multiplicative groups, e.g. matrix multiplication).

Having painstakingly established a formal proof of the product of powers, there is a notable limitation, namely that we only allow natural number exponents, \( \{x, y\} \subseteq \mathbb{N} \). In particular, we don't allow negative (e.g. -3) or fractions (e.g. 3.14159...). Indeed, the real number domain has declarative properties that evade the mere application of modus ponens in discrete logic, which gives rise to the famous satire Alice in Wonderland.

Proof sketch in real number domain

Fortunately, all is not lost in the real number domain. We can invoke Taylor's theorem to expand the infinite series for calculating \( e^x \) and \( e^y \), multiply the two series, and see if \( e^{x+y} \) expands to the result of the multiplication.

The Taylor series for \( e^x \) is:
\begin{array}{rcl}
e^x & = & \sum^{\infty}_{n=0} {x^n \over n!} \\
 & = & 1 + {x^1 \over 1!} + {x^2 \over 2!} + {x^3 \over 3!} + {x^4 \over 4!} + \dots \\
 & = & 1 + x + {x^2 \over 2} + {x^3 \over 6} + {x^4 \over 24} + \dots
\end{array}
The following table multiplies the Taylor series for \( e^x \) and \( e^y \).
\begin{array}{c|cc}
\times & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\ \hline
1 & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\
y & y & xy & x^2 y \over 2 & x^3 y \over 6 & x^4 y \over 24 & \dots \\
y^2 \over 2 & y^2 \over 2 & xy^2 \over 2 & x^2 y^2 \over 4 & x^3 y^2 \over 12 & x^4 y^2 \over 48 & \dots \\
y^3 \over 6 & y^3 \over 6 & xy^3 \over 6 & x^2 y^3 \over 12 & x^3 y^3 \over 36 & x^4 y^3 \over 144 & \dots \\
y^4 \over 24 & y^4 \over 24 & xy^4 \over 24 & x^2 y^4 \over 48 & x^3 y^4 \over 144 & x^4 y^4 \over 576 & \dots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{array}
The Taylor series for \( e^{x + y} \), expanded individually, is:
\begin{array}{c}
1 &+& (x+y) &+& {(x+y)^2 \over 2} &+& {(x+y)^3 \over 6} &+& {(x+y)^4 \over 24} &+& \dots \\
 & & || & & || & & || & & || \\
 & & x & & x^2 \over 2 & & x^3 \over 6 & & x^4 \over 24 \\
 & & y & & xy & & x^2 y \over 2 & & x^3 y \over 6 \\
 & & & & y^2 \over 2 & & xy^2 \over 2 & & x^2 y^2 \over 4 \\
 & & & & & & y^3 \over 6 & & xy^3 \over 6 \\
 & & & & & & & & y^4 \over 24
\end{array}
As you can see, the expansion of each term corresponds diagonally to the multiplication table above, so we can indeed show by Taylor expansion that \( e^x e^y = e^{x+y} \). This is only a proof sketch, but the enterprising mind could organize the table into a formal proof, using Binomial Theorem and Cauchy Product.

You might have noticed that we have only established the product law at base \(e\) but not other bases. For the other bases, recall that \( a^x = e^{x \ln a} \), so we have:
\[ a^x a^y = e^{x \ln a} e^{y \ln a} = e^{(x \ln a) + (y \ln a)} = e^{(x+y)\ln a} = a^{x+y} \]

Conclusion

There are two reasons why I suspect the Harvard entrance exam only expected the informal reasoning of counting the number of multiplicands. Cauchy (1789-1857) product is a fairly recent development to the time of the exam in 1869, which makes it unlikely to become part of the curriculum. There were no other questions that require the use of proof by induction so that it is also unlikely to be part of the curriculum either.

On the other hand, it is only after I became older (and overeducated) that I realize a lot of maths I was taught in grade school were really just informal proof sketches, and even so I didn't learn to question the profoundness of their limitations. The informal proof sketch of counting the multiplicands is limited to exponent in the natural number domain and would not work for real number exponents. I spent the better parts of my youth learning faux math!

Laws in the real number domain cannot be proven by counting alone because real numbers are uncountable. For this case I appealed to Taylor's Theorem, first expanding the polynomial series and showing the combined series are equal. I suspect many of the real number laws could use the same treatment.

How to Play Go Like a Computer Scientist

The board game of Go, or 圍棋 (weiqi), started receiving a lot of attention when AlphaGo beat the European champion Fan Hui in all of the five games. Now people are worried when AlphaGo is on its way to beat the world champion Lee Sedol, winning 3 out of 5 games so far. AlphaGo plays the game like no human as seen the game played before, inciting the awe of sadness and beauty. It is touted as an accomplishment of machine intelligence because traditionally the game of Go is very difficult for a machine to play well, whereas games like Chess is well-understood.

Board games are fascinating because a few number of rules allow an exponential number of possible game moves, some with winning outcomes, and some with losing. Traditionally, a naive game solver for any game tries all the possible positions of each alternate side's game play some number of steps ahead and chooses the first move that leads to the best gameplay after that number of steps, known as the min-max algorithm. Pruning heuristics is applied to reduce the search space so the computer does not waste time searching down "lost cause" paths, known as alpha-beta pruning. Even with pruning, the search space is still exponential to the number of positions on the board.

The keyword here is exponential. The machine can spend more time to compute, but for the amount of time spent \( t \), it can only search by \( \log{t} \) more steps. We can attempt to parallelize exponential search by enlisting the help of some number of machines, but it will still only allow us to advance the search depth by \( \log{n} \), i.e. the added intelligence is logarithmic to the number of machines.

Chess is well-understood. The number of game play combinations are vast, but we have found ways to prune the search space so that it is tractable with computer clusters that are practical to build. Computers can beat human playing Go on a smaller \( 9 \times 9 \) board with an upper bound of \( (9 \times 9)! \) or \( 10^{121} \) possible game plays, but on a professional championship level, the board size \( 19 \times 19 \) sports an exponential explosion of an upper bound of \( (19 \times 19)! \) or approximately \( 10^{768} \) possible game plays.

Even though Google might undertake the most ambitious of data center builds, they couldn't possibly shut down all the kitten videos on YouTube so AlphaGo could play against Lee Sedol with super-intelligence. Even so, they would achieve only logarithmic increase in intelligence. Building machines to brute force an exponential algorithm is a sure way to go bankrupt (NSA is an exception because the government prints the money).

I feel that a disclaimer is in order before I write any further. I don't have insider knowledge about how AlphaGo works. Everything I'm about to speculate comes from common sense and public sources.

AlphaGo algorithm reduces the search space using Monte-Carlo tree search, which means it randomly prunes some moves to reduce the branching factor, which allows the search to go deeper. The pruning is guided by deep neural network so it decreases the probability of pruning winning moves. Deep neural network works by building a hierarchy of signal processing nodes that amplifies certain signals after training.

When using DNN to recognize pictures, we can visualize how it works by looking at the images synthesized iteratively in order to boost certain signals.

In computer science, a pervasive strategy to design a super-efficient algorithm is by divide and conquer: basically, a big problem is solved by breaking down the problem into smaller sub-problems, until the problem becomes trivially solvable. Here are some examples:

• Sorting is taught to every first year computer science undergraduate. Given \( n \) items to sort, a naive sorting algorithm like bubble sort will take \( O(n^2) \) steps, whereas better ones using divide and conquer like quick sort or merge sort will take \( O(n \lg{n}) \) steps. If we are to sort 1000 items, this makes the difference between 1 million steps verses just 10000 steps.
• First year graduate student would likely learn about discrete Fourier transform. A naive DFT takes \( O(n^2) \) steps, whereas fast Fourier transform using divide and conquer takes \( O(n \lg{n}) \) steps.
• A naive matrix multiplication takes \( O(n^3) \) steps for an \( n \times n \) matrix, but Strassen's algorithm using divide and conquer takes \( O(n^{\lg{7}}) \) or approximately \( O(n^{2.8}) \) steps.
• The n-th Fibonacci number can be computed in \( O(\lg{n}) \) time using a divide and conquer method. The straightforward iterative method would take \( O(n) \) time, and a naive recursive method would take \( O(2^n) \) time. See Fibonacci Number Program for some examples in code.

For other algorithms, divide and conquer may not reduce the number of steps, but it still improves computation performance due to better cache locality. Divide and conquer is the basic idea of cache oblivious algorithms.

In other words, the real innovation of AlphaGo is not because machines achieved singularity, but because deep neural network approximated the divide and conquer method which happens to allow Go to be played efficiently.

The outcome of Go is scored by determining whether the pieces can survive locally, and the territorial occupation by the surviving pieces. This makes the winning strategy two-fold: on one hand, a player needs to ensure local survival of the pieces, but he has to take the territory into account. If a local battle is losing, it could be better for a player to strengthen his position on a different part of the board. This division of local and global thinking lends itself very well to using the divide and conquer method.

Here are some ideas how to divide. On the first level, we divide the board into subregions of \( 10 \times 10 \) each (figure left). We can also add overlapping subregions of \( 9 \times 9 \) or \( 9 \times 10 \) (figure right). This results in the first level division into \( 3 \times 3 \) subregions.

Left: Level 1

Right: Level 1 overlaps

Each subregion can be divided further into \( 5 \times 5 \) or \( 5 \times 4 \) grids with overlaps. In the following figure, only the division of the first subregion is shown, but it should be understood that the same division will take place for all first level subregions.

Left: Level 2

Right: Level 2 overlaps

A sketch of the divide and conquer algorithm would play Go by first choosing the region to play by valuation of the amount of territory it can likely occupy. Then within each region, it could brute force the positions that maximizes the survival of its own pieces.

Here is a very rough guesstimate of the number of steps needed to solve the game. These moves can be grouped into streaks of local battles taking place in \( 3 \times 3 \) subregions, and each streak is further divided to settle the \( 3 \times 3 \) sub-subregions which are about \( 5 \times 5 \) by grid. This reduces the amount of search space to be just:
\[ (5 \times 5)! \cdot (3 \times 3)! \cdot (3 \times 3)! \approx 10^{36} \]
This is a lot more computationally tractable. Of course, the caveat of my calculations is that I have never implemented a divide and conquer player for Go, and I don't know how well it works in practice. But even if we have to add a few levels of \( 3 \times 3 \) division, multiplying the search space by \( 9! \) still grows a lot slower than the exponential explosion of \( (9 \times 9)! \).
\[ (5 \times 5)! \cdot (9!)^9 \approx 10^{75} \]
Using this divide and conquer method, we can envision a game of Go played on a much bigger board, maybe like the 3-dimensional chess depicted in Star Trek.

The difference between the world champion Go player such as Lee Sedol and a modest Go player who happens to be a computer scientist, is that a computer scientist understands the power of divide and conquer. There is an immense beauty of divide and conquer that reaches far beyond game play. Nobody is worried when a computer doing quick sort can sort numbers faster than a human can with no sorting strategy, so why should we worry that a computer using divide and conquer can play a board game better than humans with only an ad-hoc strategy?

No, the computer is not about to achieve singularity. It is just a tool that helped us understand the game better.

Practicality of the Vector Packing Problem

Vector Packing problem is a generalization of the Bin Packing problem. In the simplest form, the Bin Packing problem seeks to find a placement of objects in a bin (both one-dimensional) such that the smallest number of bins are used. With vector packing, both the bin and the objects can have several dimensions, and different sizes along these dimensions.

Even in the simplest form, bin packing is an NP-hard problem. An approximation algorithm that runs in polynomial time may not produce the optimal solution, as you can see in the following illustration.

The first fit algorithm sorts objects by size, and then place each object in the leftmost bin that has space that fits. Heuristic algorithm can try harder to find a better solution at greater computation cost. You can imagine that vector packing problem is even more complex, now that the algorithm has to consider several dimensions of constraints.

Researchers understand that vector packing problem has a very useful application in cloud computing, and this has inspired a wealth of research literature. In this application, bins represent machines in a computation cluster, and each bin has a dimension for CPU, RAM, disk space, and network bandwidth. The objects represent jobs to be scheduled in the computing cluster. A job has specifications for the amount of CPU, RAM, disk, and network it uses. We can pack several jobs into a machine as long as the sum of the resources used is under what the machine could provide.

Better packing means that unused machines can be powered off to save energy, while the online machines have higher utilization which helps them achieve better energy efficiency. But as the number of jobs and the number of machines grow, even a heuristic algorithm can take a long time trying to find a better packing solution. This can grind cluster scheduling to a halt.

But I want to call this a fallacious understanding of the real problem we want to solve. In practice, cluster scheduling differs from the vector packing problem in the following regards:

• Bin or vector packing is a static problem where, once the objects are placed, they are not meant to be moved or displaced with other objects. Scheduling is inherently a dynamic allocation problem where objects come and go (i.e. they have a lifetime). An optimal packing does not imply optimal scheduling.
• The scheduling as a dynamic allocation problem is usually tackled as an offline problem where all the objects and their lifetimes are known in advance. In practice, we do not know the lifetime of jobs, which may stay running for a long time, but a human operator can always restart jobs or start new ones.
• A cluster typically have machines of a variety of specifications that differ in CPU speed, number of cores, amount of RAM, etc. Bin or vector packing assumes that all bins are of the same size.

Furthermore, in real life, job specification may not accurately reflect its actual usage. A job that says it uses a certain amount of CPU or RAM might end up using more, or using less. Or the usage may be sporadic. If it leaves garbage files around, then its disk space usage would grow indefinitely.

To define the cluster scheduling problem better, we need to understand that some of the dimensions are soft constraints, while others are hard. In general, temporal constraints are soft, while spatial constraints are hard, but there are exceptions.

• CPU is a soft constraint. If it is over-subscribed, jobs will just take longer to compute.
• Network bandwidth is also a soft constraint. If over-subscribed, then jobs will just take longer to send or receive data.
• RAM is a spatial constraint, except that can actually be over-subscribed because of virtual memory. When memory pressure is high, rarely used memory pages are swapped to disk to meet new memory demand. This swapping can cause performance issues, but it now allows a temporal trade-off, which makes RAM a soft constraint.
• In some deployment scenario, disk seek time is a scarce resource, but it is still a soft constraint. If over-subscribed, then jobs will simply spend more time waiting for disk I/O.
• The only remaining hard constraint is really the disk space.

These observations simplify cluster scheduling to become more like a one-dimensional bin packing problem, where jobs are scheduled only based on the amount of disk space it expects to use. To meet the soft constraints, we simply monitor each machine to see if the CPU, RAM, network, or I/O is oversubscribed. If so, the machine monitor will try to move contending jobs to different machines. But over-subscription will not prevent us from tentatively scheduling new jobs to run on this machine since we don't know about their performance characteristics yet; they may not cause any more contention.

It's not always a good idea trying to solve a practical problem with a theoretical one, since a theoretical solution is likely a lot harder, and will still miss the mark. Vector packing problem is not a practical representation of the cluster scheduling problem.

Questions...

A coworker sent an e-mail with a list of questions that some grade school kids have for people in the field of computer science. The questions are intriguing enough to me that I want to spend some time personally thinking about them and answering them. The questions fall under these categories: (1) personal inspiration, (2) classes or learning, (3) about the computer science field in general, (4) personal projects, and (5) women in CS. The 5th category is because the questions came from a forum focused on girls in school.

Personal inspirations

What got you into coding? What inspired you? ...

I have an uncle who worked in electric engineering. When I was in the third grade, he was the only one in our family with a computer (and a handheld camcorder). My mom brought me to his home after school, while he was still at work, and let me play with his computer, mostly games but once I drew Goemon Impact using MS Paint. I also destroyed many expensive IC chips that he kept in his drawer by my ill-conceived attempt to design my own imaginary circuit board: I didn't know about soldering, so I bent the pins to make the chips stay on the board. He wasn't married back then, so he spent many girlfriendless lonely nights unbending the pins.

For some reason he never reprimanded me. I feel very sorry every time I think back. Note to self: do not let kids play with the stuff in my drawer.

My mother was looking to learn to use the "personal computer," and she borrowed a book from my aunt about how to use MS-DOS. My mom never ended up reading the book, and for some reason the book fell into my hands. Back then, operating systems came with some programming tools, so one of the chapters in the book was about using the assembler MASM and how to diagnose programs using DEBUG.COM. These are programming tools at a very low level, very close to how the actual hardware works.

One day in third grade, my mom brought me to a computer shop with a books section, after some after-school science class that she sent me to. As I was browsing the books, I found one that says MS-DOS and programming in the title. I had no idea what was in it, but as I flipped through the pages, I accidentally ripped a page. It was a minuscule tear, but I somehow felt obligated, so I convinced my mom to buy it. I determined that I would read it enough to understand it completely so I don't waste my parent's money. The book was about the MS-DOS system architecture, and was the second volume of a three volume series. The third volume was about MS-DOS system calls and contained programming examples on how to use them. I eventually got the third volume as well, but I never went back to the first volume.

So as fate has it, my first programming language was assembly in 16-bit Intel 8086. It was as close to the hardware as it could be. I was writing instructions that perform arithmetics using machine registers and jump to memory addresses. When my program crashes, it also crashed the whole system, so I had to hit the reset button to reboot the computer. I did that many times, and the button became very polished. But if you think about it, low level systems were really simple because it had to be. Modern hardware is more complicated, but there is still a subset that is somewhat approachable.

In fourth grade, my mom sent me to a class that taught programming in BASIC. It was a rather high level but unstructured language. I think it was helpful to learn computing from both the high and the low level. Then I went to the middle and learned C, and later C++. The kind of programming I did was all pretty naive. I knew about table lookup, but didn't know about binary search or data structures until college. Data structures are about how to organize data in a computer so they could be inserted, queried, and deleted quickly. Not knowing how to organize data effectively means your program will likely run slower than it needs to. This brings us to the next topic.

Classes and learning

Why do you think it's important to study computer science? What classes should I take?

Before answering questions about classes and learning, we need to understand what computer science is about.

Computers are stupid. They follow your instructions and will do exactly that. Computer science is about how to make computers smart and more effective, so you could do more with these otherwise incredibly stupid machines. What makes computer science a prolific field is that both hardware and software can be cheaply replicated, so a good computer scientist can do great things with computers, and more by adding more computers.

For this to be possible, you need to learn about how to organize data using data structures, how to solve problems with algorithms, some theories about predicting the program's space and time requirements and other performance characteristics, how to program the computers to talk to each other, and finally, how to make sense of the programs you write.

Furthermore, not all solutions are silver bullets. A solution may perform well under a specific condition, but it might suffer a bad worst-case scenario, or it may have other trade-offs. It is important to know them so you can apply the right solution to the specific problem at hand. A college class would most likely be using sorting algorithms to illustrate these concepts. Sorting rearranges numbers so they appear in increasing order, such that the number after is always greater than the number before. Of course you could sort in decreasing order as well, but you only need to make minor changes in your sorting algorithm to do that. Or if you're a clever programmer, you implement the sorting algorithm once that can be instantiated to sort in either order, and can work with data other than numbers.

When it comes to the trade-offs of sorting algorithms, quick sort tends to be the fastest in practice, but could be very slow if the numbers are almost sorted or inversely sorted. Insertion sort is generally slow, but is fast if the numbers are almost sorted. Merge sort has no such "it depends" scenario but tends to be slower because it moves the data around more, and for a simpler implementation, uses more space.

Such trade-offs are prevalent in the field, and some people dedicate their lives to study really subtle trade-offs, when such trade-offs can still cost millions of dollars on really big problems.

Coding can be learned independently any time from books or websites, but I find that computer science concepts are better learned in a formal higher education setting, e.g. in college, and in some cases, grad school.

About the computer science field in general

What do you find most challenging? What do you think the computers will be like in the next 50 years?

Remember, computers are incredibly stupid machines. The computers these days appear smart only because some dedicated computer scientists figured out how to make them so. I am of the opinion that computers can only be as smart as the person programming them; and that even if someone figures out how to make computers program themselves, the cumulative result of computers programming itself to program itself will converge to a finite limit. Of course, that means that computer scientists cannot be replaced by computers, so that guarantees some job security!

The difficulty is trying to figure out what problems there are left to solve. Many problems such as sorting, data structures, networking, and even distributed computing have good enough solutions, which means the likelihood of breakthrough is small. There are some open problems pertaining to computer vision and artificial intelligence. Some problems are interesting in a theoretical sense but difficult to prove. An example is the P =? NP problem: whether a deterministic machine (computation happens in a single sequential universe) has less computing power than a non-deterministic machine (computation happens in unlimited number of parallel universes). It's still unsolved.

Cryptography is another highly anticipated field. It's about information security, so that only the intended parties may exchange messages, and no other parties can figure out what the messages are even if they are intercepted. The assumption of cryptography is that it would be computationally expensive to decrypt a message without knowing some secret. But computers are getting faster, which makes it easier to guess the secret. The challenge there is to find different ways to encrypt a message that still makes it computationally infeasible to decrypt without the secret.

My personal conviction is to improve the way we understand programming so that programs are easier to understand and less error-prone. But again, this is also a very mature field with mixed results. There is some potential for advancement, but it's not clear how it's going to be.

Personal projects

What kind of things do you program? What programming language do you use?

I am currently trying to understand limitations of existing programming languages in order to find new language design or paradigm that would alleviate these limitations. The limitations aren't about the computation power, but it's about how to write programs and reuse them more straightforwardly. I'm writing an assortment of common routings in C++ that might help me identify these opportunities.

Women in CS

What does being a women in CS entail for you? What are some challenges you have encountered as a woman in CS?

Unfortunately I cannot speak for women in CS because I am not a woman. But I love giving the example of Ada Lovelace as the first programmer in history, a woman. She was studying mathematics under Charles Babbage because her mother thought it would remedy a family history of mental illness from her father's side. Charles Babbage designed the first analytical engine, a computer made of gears and shafts. He never built them, but in recent years the Computer History Museum have built one according to his original design and demonstrated that it worked.

Computer science is a gender neutral subject, but as in any field, minority groups may be subject to political discrimination for any number of things from acceptance of academic papers for publication to salary and promotion. Women are not the only discriminatory group. Being a Chinese, I think we are discriminated in some ways as well. Once I submitted a paper for review---it was only single blinded which means I do not know the reviewer, but the reviewer can see my name---and a reviewer made a non-sense comment about my grammar as a reason for rejecting my paper.

I think there is also a difference on the learning process between male and female. My hypothesis is that males are more accustomed to unstructured learning (i.e. figuring things out yourself) while females benefit more from structured learning (i.e. in a classroom with a course plan and assignments). Since computer science is a discipline that arose in the last 50 years or so, which is nascent compared to literature, mathematics, or even natural sciences, we have still yet to develop effective structured education, which may cause more women to struggle through the study. This situation will likely improve especially when teachers start to import computer science into the high school curriculum. College professors are definitely the subject expert, but grade school teachers know more about education theory and effective teaching than college professors.

Closing remark...

If you found this blog post because you are a young student looking to enter the field of computer science, I hope this is helpful to you. If you are a computer science veteran, I welcome your feedback.