Paul Nicholls Stuff

30May/090

Peer To Peer Networking

In a peer to peer (P2P) network every machine can communicate directly with every other machine in a network. No computers have any more authority than others. This is in direct contrast to client-server architecture.

peer-to-peer (or P2Pcomputer network uses diverse connectivity between participants in a network and the cumulative bandwidth of network participants rather than conventional centralized resources where a relatively low number of servers provide the core value to a service or application.

http://en.wikipedia.org/wiki/Peer-to-peer

25May/091

Context Sensitive Languages

A language is context-sensitive if it is recognised by a Linear Bounded Automaton (LBA). An LBA is a non-deterministic single-tape Turing Machine that can only use part of the tape (the tape is bounded).

There are basically no practical applications for Context-Sensitive Languages.

Tagged as: , 1 Comment
25May/090

The Turing Machine

The Turing Machine was first proposed by Alan Turing in 1936 as the first rigorously definied model of computation. It is essentially the foundation of modern computers and can do everything that a real computer can do. It was not ever intended for construction, but is more of a thought experiment.

A Turing Machine (TM) has an infinite tape (memory), with a tape head that can read, write and move around on the tape. There is also a finite-state program comprised of a table of instructions which controls the tape head.

Tagged as: , Continue reading
25May/090

Context-Free Grammars

Context-Free Languages (CFLs) are more powerful than Regular Languages (provably so) and can be defined by means of Context-Free Grammars or Push-Down Automata. Any context free language can be represented with either of these methods. CFLs closely relate to both human languages and programming languages and their applications tend to fall within these fields.

A Context-Free Grammar (CFG) is essentially a collection of substitution rules of the form A \rightarrow b where A is a variable (or nonterminal symbol) and b is a string of terminal and nonterminal symbols.

Tagged as: , Continue reading
25May/090

Push-Down Automata

Push-Down Automata (PDAs) are an example of a Context-Free Language, they make use of a stack containing data and have to power to make transitions based on the top of the stack, and also manipulate the stack by popping and pushing new values. They are essentially an implementation of NFA's with an additional stack.

Put together: Given an input signal, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack.

http://en.wikipedia.org/wiki/Pushdown_automaton

Tagged as: , Continue reading
17May/090

Rules of Inference

Proof Theory allows the representation of mathematical proofs facilitates the analysis of proofs by expressing them syntactically.  For example, in the sequent below the formulas \phi _1 \ldots \phi _n allow us to conclude \psi . Such a sequent is valid if it can be proved.

\phi_1 \ldots \phi_n \vdash \psi

We can form a collection of proof rules which allow us to infer new forumlae from existing ones. These inference rules are a relation between premise formulae and conclusions. Such rules take the general form:

\begin{array}{l}\underline {\begin{array}{*{20}c}{\phi_1 \mbox{ Premise 1 } }  \\\ldots   \\{\phi _n \mbox{Premise 2 }}  \\\end{array}} \\\psi \mbox{ Conclusion }\\\end{array}name of rule