Tag Archives: algorithm

October 26, 2015

System Code

os-0 We started with mathematical expressions, abstract algorithms, and the idea of code — a list of instruction steps in some code language. We touched on how all algorithms have an abstract state diagram (a flowchart) representing them. Then we looked briefly at the stored-program physical machines that execute code.

Before we go on to characterize the complexity of a computer, I want to take a look — very broadly — at how the computer operates overall. Specifically, look at another Yin-Yang pair: the computer’s operating system versus its applications.

This has a passing relevance to the computer’s complexity.

20 Comments | tags: algorithm, application code, computer program, hardware, O/S, operating system, software, stored program computer, system code, user code | posted in Computers

October 23, 2015

Running Code

By Wyrd Smythe

VN architecture We started with the idea of code — data 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…

17 Comments | tags: address bus, algorithm, assembly language, bits, code, computer language, computer program, CPU, data, data bus, RAM, source code, stored program computer, Von Neumann architecture | posted in Computers

October 21, 2015

Coded Math

By Wyrd Smythe

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…

2 Comments | tags: Alan Turing, algorithm, Church-Turing thesis, code, data, flowchart, lambda calculus, state diagram, stored program computer, Turing Machine, Universal Turing Machine, Von Neumann architecture | posted in Math

October 20, 2015

Calculated Math

By Wyrd Smythe

calculation-0 The 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.

13 Comments | tags: Alan Turing, algorithm, binary digits, calculation, Church-Turing thesis, code, computer program, data, information theory, lambda calculus, mathematical expression, Turing Machine, Universal Turing Machine | posted in Math, Opinion

October 19, 2015

Sideband #58: Halt! (or not)

By Wyrd Smythe

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.

10 Comments | tags: Alan Turing, algorithm, calculation, Cantor's Diagonal, discrete mathematics, Halting Problem, Turing, Turing Halting Problem | posted in Computers, Sideband