Download paper. [gview file=”https://www.yodaiken.com/wp-content/uploads/2016/01/practical.pdf”]
Theories of abstract automata – Arbib
We have said that automata theory deals with the realization of partial functions F: X* —» Y* by some finitely specifiable substrate. Before we specify in more detail the forms (of which the Turing machine is one) of substrate which
Algebra for computer science and function nesting
The fundamental mathematical basis of computer science is that code and data are the same things. A sequence of bits can represent real numbers, integers, vectors, groups, matrices, video , audio, or programs, algorithms or even proofs. When we try
Primitive recursion over words
From: @book{Peter:1982:RFC:539249, author = {Peter, Roezsa}, title = {Recursive Functions in Computer Theory}, year = {1982}, isbn = {0470271957}, publisher = {Halsted Press}, address = {New York, NY, USA}, }
Pointers draft
Despite pedants, pointers are useful and interesting and if you don’t understand them, you don’t really get what’s going on in a computer. Think of memory as a function $latex M: N\to N$ where $latex N$ is the set of
Fischer Lynch Patterson and timeouts
There is a widely cited (over 1400 cites in CiteseerX ) result called the Fischer-Lynch-Patterson theorem about consensus – a key issue in distributed databases or any system where data is either distributed or replicated or both. In this paper, we
A hard theorem becomes easy over time.
The basic result of the incompleteness proofs is pretty simple. The proofs are complicated because the idea was literally unthinkable until programming was invented. The heroic efforts of Gödel, Skolem, Post, and Church to create a mathematics in which doing mathematics
the terrible effect of Krohn-Rhodes
One of the most interesting theorems in computer science is the Krohn-Rhodes theorem that shows a strong link between basic computer science and group theory. Crudely, the KR theorem extends Jordan-Holder \( (H_1 \triangleleft H_2 … \triangleleft H_n=G)\) to state
Gödel’s Lost Letter
Gödel’s perspective in this letter is a refutation of the simplistic take on Turing’s proof seen so often in the computer science literature. In particular: After all, one would simply have to choose the natural number n so large that
Are threads evil? (updated)
This paper by Prof. Edward Lee explains something of why “threads” are such a painful abstraction. As Prof. Lee notes, threads intrinsically create unspecified program operation (which he calls non-determinism) and resource conflicts which we then attempt to “prune” via