DJ Strouse

My Goodreads Rating: 2 of 5 stars

Reading this book was a bit like listening to my grandpa rant about LBJ’s foreign policy decisions – he’s probably right, but without the background to appreciate his frustrations, all I can do is listen and squirm awkwardly in my chair.

Batchelor’s book is a polemic against the modern transformation of Buddhism into something as dogmatic and unquestioning as Western religions. He points out that Buddhism is a personal practice of continual awareness and questioning, not a set of beliefs, commitments, or rituals. His insights into Buddhist practices were thought-provoking but being a man of science (and therefore atheist, culturally bankrupt, anti-humanities of course), I didn’t have the religious or historical background to appreciate many of his complaints about the disfigurement of Buddhism.

This short book is meant to be read slowly. Each chapter offers ideas worth taking the time to reflect upon and some also suggest particular meditations. Unfortunately, I was borrowing this from a friend at university and had to power through it in two evenings before leaving for the summer.

I likely won’t return to this book again though, because my interests in Buddhism are related to cultivating continual awareness, not in defending it against a deplorable watering down for the masses.

View all my reviews >>

Tags:   buddhism · philosophy · religionNo Comments.

My Goodreads Rating: 3 of 5 stars

I dove into this book excited to learn how the minds of great scientists churn but instead was reminded of the great danger that accompanies reading old science texts – lengthy discussions of crackpot theories (i.e. phrenology) and passionate defenses of well-accepted ideas (i.e. not all mental activity is conscious). Taken as a survey of late 19th/early 20th century thinking on creativity and thought, the book reveals how stubbornly we humans cling to the mech warrior hypothesis of behavior – that every nugget of our activity stems from the conscious control of a homunculus nested in his HQ and peering out of our eyes like little windows on a spaceship. Many psychologists and philosophers quoted by Hadamard actually deny the existence of nontrivial unconscious processing in creative thought. If this doesn’t shock or disgust you and you find yourself sympathizing with this notion, go directly to jail. Do not pass Go. Do not collect $200.

Even so, this short book is worth a skim – the survey questions in the appendix alone are worth the price of admission. Hadamard used these questions to drill all his scientist/mathematician buddies on how they think, imagine, and work. The list is even more than a set of questions though – its a set of suggestions. If you’re as narrow-minded and habituated as I am, you’ll likely discover entirely new ways to approach problem-solving and find yourself exclaiming, “People think like that?!” I highly recommend reading the survey before the book itself, as this will get you thinking ahead of time about how you think and offer more context for understanding and possibly assimilating the habits of Hadamard’s buddies.

The writing (or at least the translation) is also pretty amateurish. Parts of this book read like the dinner table reports of a 4th grader telling his mommy and daddy what all his friends did in class today… except instead of eating boogers and tricking Suzy into thinking she was adopted, Hadamard’s friends invent special relativity, bifurcation theory, and cybernetics.

If you can tolerate or skip the many faults of this early thought experiment on thought, however, you’re sure to not only learn something about the great minds of the late 19th/early 20th century, but your own feeble brain as well.

Book Notes (Warning: not guaranteed to be interpretable to outside eyes):

• Invention is combination followed by selection.
  • Selection is the more difficult step.
  • The selection process seems highly emotional. Understanding the emotional character of selection would teach us much about invention.
• Two benefits of incubation:
  1. reset (replenishment of mental resources)
  2. restart (retract assumptions and avoid mental ruts)
• The incubation paradigm changes the role of the scientist to that of a mental farmer – toil hard in the fields of conscious effort (and failure), then later reap the benefits brought on by subconscious processing.
• Ways mathematical minds may differ:
  • accessibility of thought/depth in unconscious (logical vs. intuitive thinking)
  • narrowness of thought (logical vs. scattered)
  • different auxiliary representations (geometric, verbal, auditory, etc)
• Two kinds of invention:
  1. Set goal, seek means
  2. Discover means, seek application (more common in mathematics)
• I wonder how many grand ideas remain just out of reach in the antechambers of the minds of geniuses, perhaps consciously acknowledged but under-appreciated by them, perhaps tacitly assumed, or perhaps subconscious and nebulous.
• The scientist whose aesthetic sense (passion) draws him to discoveries with profound implications is what we call a genius.

View all my reviews >>

Tags:   brains · creativity · invention · mathematics · philosophy · psychology · thoughtNo Comments.

The Zealot King Problem
Let’s say you’re the king of a far-off land inhabited by Turing machines. As a highly religious king, you have strict morals and lately, you’ve been frustrated to see many of your citizens acting immorally. You’ve been especially aghast at their frequent and flagrant violation of restriction R. Restriction R isn’t a law, but you simply find its violation morally repugnant. Your department of mad scientists has shown that Turing machines operating under restriction R are just as powerful as those that don’t, so you don’t feel bad about taking away your citizen’s privileges to break restriction R. Thus, the religious zealot you are, you do it; you declare a law that no Turing machine may violate restriction R on any input.

Now you need to enforce your law. You need to make a Turing machine police force that runs around testing passerbys to see whether they are upstanding, R-abiding Turing machine citizens. Can you do it?

Further Motivation for the Theoretical CS Junkie
After an awesome course in mathematical logic with Len Adleman at USC that flirted with issues of computability, I’ve been addicted to theoretical CS textbooks, including Michael Sipser’s excellent Introduction to the Theory of Computation. One exercise (5.28) introduces Rice’s theorem, which states that the question of whether or not a Turing machine’s language has some non-trivial property is undecideable. But this only holds for “linguistic” properties – those of the Turning machine’s language. You might wonder (at least I did), what about “operational” properties?

Certainly there are some operational properties we can decide. Does [insert your favorite Turning machine here] move left on step 6 for any input of length 10? Beats me, but I could sure simulate your Turing machine for 6 steps on each of the n^10 strings of length 10 (where n is the number of symbols in your tape alphabet) and check.

But there are plenty more operational properties that we can’t decide. I was interested in identifying the conditions that make an operational property undecideable, and I’ve at least found a sufficient set.

I post this little result here for several reasons:

1. Someone has very likely already cooked up a much tighter solution to this (or a similarly stated) problem already.  If anyone reading this knows of such work, please point it out!
2. I’m a TCS noob and would love for someone to prove my conditions wrong.
3. Is there a more general set of conditions than the ones I give?  Are there other more interesting tweaks to Rice’s theorem?  Any ideas here are welcome.
4. I’m a sucker for open science.

Formalism & Proofs
First, let’s define two conditions that the restrictions we will consider must have.

Definition 1: A restriction R is “gentle” if for every Turing machine T, there exists another Turing machine T2 that operates under the restriction R and recognizes the same language as T.

In other words, R does not reduce the power of Turing machines.

Definition 2: A restriction R is “non-expiring” if, given any Turing machine T and input w, there does not exist a number of steps N such that if T has run for N steps on w without halting, it is no longer possible for T to violate R.

In other words, R can be violated at any point in a computation and there is nothing a Turing machine can do to “lose” the opportunity to break R, besides halting.

Lemma: Given a “gentle” restriction R, it is possible to create a Turing machine S that never violates R and upon input <T,w>, where T is a Turing machine and w is some string in the tape alphabet of T, S simulates T on w.

Proof:
Its well-known that we can create a universal Turing machine U that given inputs of the type <T,w> simulates T on w (if you don’t believe me, go try to do it yourself or check out Wikipedia). By the definition of “gentle”, we can also create U2 that operates under restriction R and for inputs <T,w>, simulates T on w. This U2 is our desired S.

Theorem: Given a “gentle” and “non-expiring” restriction R, the language BEHAVED = {<T>: T is a Turing machine that does not violate R on any input} is undecideable.

Proof:
We’ll prove this by reduction to the halting problem, described by the language HALT={<T,w>: T is a Turing machine and T halts on w}. That is, we’ll assume we have a Turing machine deciding BEHAVED and build one that decides HALT.

Let B be a Turing machine that decides BEHAVED. Construct the following machine H that decides HALT.

H= “On input <T,w>,

1. Construct the following machine N.  On any input x,
   1. Run R-abiding simulator S (from the lemma) on <T,w>.
   2. If S accepts, violate R and halt.
   3. If S rejects, violate R and halt.
2. Run B on <N>.
3. If B accepts <N>, reject <T,w>.
4. If B rejects <N>, accept <T,w>.”

If S halts (accepts or rejects), N violates R and halts.  If S doesn’t halt, N never violates R and doesn’t halt.  So N violates R if and only if S halts.  By definition, S halts if and only if T halts on w.  So N violates R if and only if T halts on w.  Also, by definition, B accepts <N> if and only if N does not violate R for any input.  So B accepts <N> if and only if T does not halt on w.  So by steps 3 and 4 of H’s description, H decides HALT.

Justification of “Gentle” and “Non-Expiring” Conditions
I needed the “gentle” condition for the lemma.  If the restriction actually reduces the power of Turing machines, the above method of building some Turing machine simulator that operates under that restriction and only violates it to signal some particular situation (i.e. halting) won’t work, since the simulator won’t be universal.

I needed the “non-expiring” condition to make sure that when S finishes simulating T on w, its still possible for N to violate R.  This condition kicks out those easily decideable restrictions that I mentioned earlier.

Any suggestions on tweaking these conditions are welcome.

Some Examples of “Gentle”, “Non-Expiring” Restrictions
Turing machines are robust little guys and we can come up with plenty of plenty of restrictions that won’t reduce their power. Here are some examples mostly adapted from Sipser’s text:

• Only move left to “reset” like a typewriter (that is, if you want to move left, you have to go all the way to the left edge of the tape and then work your way to the right again).
• No writing on multiple tapes (for instance, we could lay out several tapes to “tempt” a Turing machine, then demand that it only use one).
• No exploiting non-determinism (similarly to the multi-tape case, we could give a Turing machine the option of “branching”, then demand it not do so).
• Alter each tape square only once.
• No using squares of a doubly infinite tape to the left of some given square (that is, we give a Turing machine a doubly infinite tape, then demand it not cross a certain boundary, effectively restricting it to the usual semi-infinite tape).

I’m sure you can come up with many more and feel free to share your favorites.

Tags:   computability · theoretical computer science · turing machinesNo Comments.