Tags / Computer Science

Generalizing Dynamic Programming

Using dynamic programming techniques to optimise general compute efficiency

Dynamic programming is an approach to efficiently implementing certain classes of algorithms. As a feeble excuse for not noticing this earlier, the term is a little confusing: it isn’t about programming or about doing it dynamically! It was invented in the 1950s by Richard E. Bellman whilst working for RAND Corporation. Apparently he deliberately named it obtusely to avoid his work being considered research! I discovered this term recently when looking into existing research about algorithm optimisation and specifically why the systemic memoisation in NetKernel can optimise solutions to certain problems particularly well. [Read More]

Travelling Salesman Problem

Study of TSP running on NetKernel with cache replacing dynamic programming

This paper offers an analysis of the application of NetKernel and Resource oriented computing to the well known Travelling Salesman Problem (TSP). This discussion ignores the many approximate approaches to solving this problem which are necessary for real-world problems of any significant complexity. The aim, however, is to show how ROC can automatically optimise a solution which it knows nothing about other than empirical data collected during execution. The algorithm structures the problem into sub-problems many of which overlap with each other - this occurrence is called overlapping subproblems. [Read More]

History Of Gödel Numbering Part 3

This is the third and final article in this series. Part 1 and part 2 describe how the concept of Godel numbers were first used to solidify the foundations of computing, then subsequently neglected by mainstream computing as it evolved until research at Hewlett Packard showed how the concept could lead to the caching of pure computation. In this final part I want to show the implications of this discovery for the future of IT. [Read More]

History Of Gödel Numbering Part 2

In the first post in this series I introduced Godel numbers and the important role they had in the foundations of computing. In this post I want to show how we took the concept to pioneer an approach to cache computation. A technique of identifying and eliminating redundant processing. Please entertain my third person prose. Picking up the trail In 1999 a small group of researchers in Hewlett Packard Labs were working in the domain of e-payment and digital commerce. [Read More]

History Of Gödel Numbering Part 1

At the break of the 20th century the prominent German mathematician, David Hilbert, posed 23 unsolved mathematical problems. He believed these problems were critical to progress in the field. Many, but not all of these problems have since been solved and some have given great philosophical insight. In particular his second problem asks for a proof that arithmetic is consistent, that is the arithmetic that we learn at school and forms the basis of much of the social and economic structure of our society. [Read More]

Practical State Machines in NetKernel

Following up on my previous post, ROC Hockey, where I introduced our new implementation of Hierarchical State Machines on NetKernel I’ve decided to cover the topic of how they are actually used in practice in an ROC system. Since that post we have released the first version of Lang/SCXML urn:com:ten60:netkernel:lang:scxml into the Enterprise Edition repositories. If you want to have a play with it yourself here are the steps:

[Read More]

ROC Hockey

As respite from soap-boxing, this week I have a technology demo that was built to provide a testing ground for some new technology I’ve been working on - state machines. State Machines have long been used for embedded systems as a programming abstraction that provides a tight language for programming systems that have well defined modes. They fit a certain class of problems very well and can help provide robust solutions in scenarios where other approaches rapidly become riddled with corner cases and become difficult to test. [Read More]

Rich Representations

Resource representations: they capture a snapshot of the state or intended state of a resource. When you think of REST it’s natural to think of resource representations as a stream of binary data sent over a network ready to be consumed by a client. However, except in the degenerate case of serving static data and downloading it to your hard disk, that representation must always be “serialized” by the server and “parsed” by the client. [Read More]