Tag Archives: algorithm

Interpreting AND as OR

Previously, I wrote that I’m skeptical of interpretation as an analytic tool. In physical reality, generally speaking, I think there is a single correct interpretation (more of a true account than an interpretation). Every other interpretation is a fiction, usually made obvious by complexity and entropy.

I recently encountered an argument for interpretation that involved the truth table for the boolean logical AND being seen — if one inverts the interpretation of all the values — as the truth table for the logical OR.

It turns out to be a tautology. A logical AND mirrors a logical OR.

Continue reading


Math Games #1

Back at the start of March Mathness I promised the math would be “fun” (really!), but anyone would be forgiven for thinking the previous two posts about Special Relativity weren’t all that much “fun.” (I really enjoy stuff like that, so it’s fun for me, but there’s no question it’s not everyone’s cup of tea.)

Trying to reach for something a bit lighter and potentially more appealing as the promised “fun,” I present, for your dining and dancing pleasure, a trio of number games that anyone can play and which might just tug at the corners of your enjoyment.

We can start with 277777788888899 (and why it’s special).

Continue reading


The Next Fire

Fareed ZakariaCredit where credit is due, both the major ideas in this post come from Fareed Zakaria on his CNN Sunday program, GPS. If you follow TV news at all, you know Sunday mornings have such long-running standards as Meet the Press (on NBC since 1947!) and Face the Nation (on CBS since 1954). (Or was it Meet the Nation and Face the Press?)

Zakaria is one of the good ones: very intelligent, highly educated, calm and measured. He’s well worth listening to. (I’ve realized one attraction to TV news is the chance to — at least sometimes — hear educated, intelligent talk. It’s a nice respite from most TV entertainment.)

Two things on Zakaria’s last episode really rang a bell with me.

Continue reading


Turing’s Machine

state diagram 1aNo, sorry, I don’t mean the Bletchey Bombe machine that cracked the Enigma cipher. I mean his theoretical machine; the one I’ve been referring to repeatedly the past few weeks. (It wasn’t mentioned at the time, but it’s the secret star of the Halt! (or not) post.)

The Turing Machine (TM) is one of our fundamental definitions of calculation. The Church-Turing thesis says that all algorithms have a TM that implements them. On this view, any two actual programs implementing the same algorithm do the same thing.

Essentially, a Turing Machine is an algorithm!

Continue reading


Model Code

phrenologyThe ultimate goal is a consideration of how to create a working model of the human mind using a computer. Since no one knows how to do that yet (or if it’s even possible to do), there’s a lot of guesswork involved, and our best result can only be a very rough estimate. Perhaps all we can really do is figure out some minimal requirements.

Given the difficulty we’ll start with some simpler software models. In particular, we’ll look at (perhaps seeming oddity of) using a computer to model a computer (possibly even itself).

The goal today is to understand what a software model is and does.

Continue reading


Running Code

VN architectureWe started with the idea of codedata consisting of instructions in a special language. Code can express an algorithm, a process consisting of instruction steps. That implies an engine that understands the code language and executes the steps in the code.

Last time we started with Turing Machines, the abstract computers that describe algorithms, and ended with the concrete idea of modern digital computers using stored-programs and built on the Von Neumann architecture.

Today we look into that architecture a bit…

Continue reading


Coded Math

Is that you, HAL?

Last time, in Calculated Math, I described how information — data — can have special characteristics that allow it to be interpreted as code, as instructions in some special language known to some “engine” that executes — runs — the code.

In some cases the code language has characteristics that make it Turing Complete (TC). One cornerstone of computer science is the Church-Turing thesis, which says that all TC languages are equivalent. What one can do, so can all the others.

That is where we pick up this time…

Continue reading


Calculated Math

calculation-0The previous post, Halt! (or not), described the Turing Halting Problem, a fundamental limit on what computers can do, on what can be calculated by a program. Kurt Gödel showed that a very similar limit exists for any (sufficiently powerful) mathematical system.

This raises some obvious questions: What is calculation, exactly? What do we mean when we talk about a program or algorithm? (And how does all of this connect with the world of mathematics?)

Today we’re going to start exploring that.

Continue reading


Sideband #58: Halt! (or not)

Hamlet 2B or Not 2B

evaluate(2B || !2B)

Hamlet’s famous question, “To be or not to be?” is just one example of a question with a yes/no answer. It’s different from a question such as, “What’s your favorite color?” or, “How was your day?” What it boils down to is that the young Prince’s question requires only one bit to answer, and that bit is either yea or nay.

Computers can be very good at answering yes/no questions. We can write a computer program to compare two numbers and tell us — yea or nay — if the first one is bigger than the second one. Computers are also very good at calculations (they’re just big calculators, after all). For example, we can write a computer program that divides one number by another.

But there are questions computers can’t answer, and calculations they can’t make.

Continue reading