Skip to main content

Computation

RSS feed

Converting a stream of binary digits to a stream of base \(n\) digits

James Coglan asked on twitter:

https://twitter.com/jcoglan/status/212163174626115584

https://twitter.com/jcoglan/status/212163325579108353

So you have an infinite stream of uniform random binary digits, and want to use it to produce an infinite stream of uniform random base \(n\) digits.

The obvious really easy way to do it is to find the smallest \(k\) such that \(2^k>=n\), and generate numbers in the range \(0 \dots 2^k-1\).

If the number you generate is less than \(n\), yield it, otherwise chuck it away.

This works, but has the problem that you might go a long time before you generate a number that you don’t throw away.

So what can we do with the numbers that are thrown away?

Subtract \(n\) from them, and use them as a stream of infinite base \((2^k-n)\) digits.

You can then do the same trick of generating enough of those digits until you can generate numbers greater than or equal to \(n\). Numbers less than \(n\) are yielded; otherwise, the trick is repeated yet again!

Read more…

Not-quite-slides from a talk about Turing completeness

Today I gave a talk to the department’s Postgrad Forum about Turing completeness, and universal computers. I couldn’t be bothered fiddling with Beamer to create a PDF slideshow, and I wanted to include some Youtube videos in my talk, so I made up my “slides” in HTML with a bit of CSS so it looks nice. MathJax provided LaTeX support for the maths I needed to write. The end result is a long page that I scrolled down as I talked. It seemed to work as well as a proper slideshow would’ve.

Here’s the page, which doesn’t make much sense without the talking to go along with it, and here’s the CSS file I made, in case anyone else fancies doing the same thing.

Computable categories

So I read a bit about categories after Peter Hines came up to talk to us.

Categories

A category \(C\) is a collection of objects \(obj(C)\) (or just Obj), a collection of arrows (or morphisms) \(hom(C)\) (or just Hom), and an arrow composition operation \(\circ\) such that there is an identity arrow for each object.

An arrow has a single source object and a single target object, and is written \(A \overset{f}{\rightarrow} B\).

Read more…

The computability of a fgoagog (intro)

I’m going to write up a result I think I’ve proved, which follows on from Gatterdam’s thesis. He showed that if a group is \(E_n\) computable, then doing a free product with amalgamation or any number of HNN extensions to it results in a group which is at worst \(E_{n+1}\) computable. What I’m going to say is that the fundamental group of a graph of \(E_n\) groups is at most \(E_{n+1}\) computable. This isn’t unreasonable, because a fgoagog (( ‘fgoagog’ is short for ‘fundamental group of a graph of groups’, because I can’t be doing with writing that out once every three minutes )) represents a load of HNN extensions and amalgamated products.

The tactic will be to follow Gatterdam’s method for amalgamated products – if we can find an algorithm which solves the word problem of the fgoagog (decides if a word on the generators is equivalent to the identity) in \(E_{n+1}\) time, then the whole group is \(E_{n+1}\) computable as a quotient of the free group by the set of trivial words.

I will define an admissible form for words from the fgoagog, which is an alternating series of edge letters and words from the vertex groups, such that the edge letters make up a cycle starting and ending at the base vertex. Once we have a word in admissible form, we can reduce it by swapping the image of an edge group in one vertex with its counterpart in the vertex at the other end, and eventually a trivial word will end up as just a word on the base vertex, which is an \(E_n\) decision.

Clearly the process of putting a word in admissible form involves knowing something about the shape of the graph, so we need to make some \(E_n\) computable functions which can represent the graph and compute paths between vertices. That’s a tiny bit interesting on its own, so I’ll spend my next post talking about that. It will need some pretty pictures of trees though, which is why I’ve put off writing it for so long.

Groups and the Grzegorczyk Hierarchy

Right, so I’ve written about computable groups and the Grzegorczyk hierarchy previously. Now it’s time to join the two together so we can talk about the computational complexity of certain groups.

\(E_n\) computable groups

Let \(G\) be a group with an admissible index \(i\) and corresponding multiplication function \(m\). If \(i(G)\) is \(E_n\) decidable (( there is an \(E_n\) computable function which returns \(1\) on numbers which are indices of elements of \(G\), and \(0\) otherwise )) and \(m\) is \(E_n\) computable, then \(G\) is said to be \(E_n\) computable.

We can also add the characteristic function (( \(c_A\) such that \(c_A(x) = 1\) if \(x in A\), and \(0\) otherwise )) of a particular set to the primitive functions in the Grzegorczyk hierarchy to make some arguments about group computability easier. If we have \(c_A\), the characteristic function of the set \(A\), to our hierarchy, then we say a function (or group) is \(E_n(A)\) computable ((or “\(E_n\) computable relative to \(A\)”)) if it can be obtained from composition and bounded recursion on \(E_n\) functions and \(c_A\).

Read more…

Computable Groups

This is Rabin’s definition of computable groups. There’s a slightly different version by Mal’cev but I haven’t read it and Rabin seems the most popular from my perspective.

Computable functions and sets

Very quickly: the primitive recursive functions are the class of functions that starts with the same primitives as the Grzegorczyk hierarchy, closed under composition and unbounded recursion. The recursive functions are the primitive recursive functions also closed under minimalisation, the operation which gives you the least \(n\) such that some \(P(n)=1\) (( “the least x such that P(x) holds” is written \((mu x)[P(x)]\) )) . Because those all sound like fairly possible things to do, recursive functions are also called (effectively) computable functions.

For any subset \(S \subseteq \mathbb{N}\) of the natural numbers, one can define a characteristic function \(c_S(n)\), which takes the value \(c_S(x)=1\) when \(x \in S\), and \(0\) otherwise. A set \(S\) is said to be recursive if its characteristic function \(c_S\) is recursive.

Read more…

The Grzegorczyk Hierarchy

Now to the other end of the subject, computational complexity. The two ends aren’t going to meet in the middle, but the Grzegorczyk Hierarchy is so simple it should be at the start by natural justice, and it’s good to have in mind as a pleasant ending point while getting lost in pregroup theory.

If you want to ask yourself whether a problem is computable or not, you have to define what you mean by ‘computable’. It’s left as an exercise for the reader, basically. So the popular thinking is that effectively computable functions and recursive functions are the same thing – that is, every computable function should be recursive.

Furthermore, a slightly smaller class of functions, the primitive recursive functions, contains pretty much everything anyone’s interested in, and leaves out horror shows like the Ackermann function.

The idea is that you can start with a few really simple initial functions: zero; successor; projection, and the operations of composition and recursion, and end up with pretty much every function on the natural numbers that anyone’s ever thought up. (( before this was claimed and people tried to think of things that weren’t included in this class, anyway ))

A primitive recursive function is one which can be defined by finitely many compositions and recursions on the initial functions. A generally recursive function can be defined using unbounded minimisation as well, but remember that we’re deliberately ignoring those.

Read more…