Fruitbox

A few days back, this crossed my thought: We interact with our computers through a keyboard that has quite a number of keys. We can do the same things, albeit not as comfortably, on our mobile phones, which traditionally only has about 1/10th the number of keys as a full computer keyboard. If we take this to the extreme; How many keys are needed to control a computer, the way they work today?
This is a nice case to apply the principle of reduction and emulation to. If we have a device which can emulate a computer keyboard, it can control the computer, since the regular computer keyboard can.
Step 1: Consider a device with only arrow keys and an enter key. To control a computer with this device we would only need to have an on-screen keyboard program, where we navigate to the key we want to press and hit enter.
Step 2: Now we don’t really need that many arrow keys. One is really enough: the “forward” key. Think of a keyboard represented linearly, and when we move to the end we get back to the beginning. Although neither convenient nor practical, we can now control the computer with two keys.
Step 3: Why have two keys when we only need one? After all, two keys to remember is even TWICE as many as having only one key. Let the software program switch selected key every second, and you press the enter key when the key you want is highlighted. Or alternatively, make a double-click equivalent function, but then this could be treated as having two keys.
Conclusion: We only need one key, which I think should referred to as “the any key”.

Did you know: There is a well kept secret in the history of computing: The first keyboards only had one key (bet you didn’t know that, eh?) After all, keep it simple is nice, isn’t it? Why design a complicated piece of hardware when you can have a big, easy-to-hit, RSI monster like the one-key keyboard. If you wanted to, you could even make it really small. You didn’t even have to learn touch typing or anything like that! But no, it wasn’t until someone invented the cracks between keys that things got more complicated.
Remark: This blog post is copyright(c) 1956-2009, written on a one-key keyboard.

As the title says, I am going to write about customising LaTeX to work with Swedish typographical rules and conventions. The articles will be in Swedish and will be on my Swedish blog, Fruitbox 2.

Today I am going to present one of the worst sorting algorithms, along with a C# implementation. The algorithm is called bogosort, also known by other names such as monkey sort, random sort or shotgun sort. This algorithm is very simple, and it works as follows:

1. Given a random array, check if it is sorted.
2. If it is not sorted, shuffle it randomly.

As you can imagine, this algorith is not very fast, but it CAN be very effective, and for an array just consisting of two elements, it is actually very nice. Despite this, don’t use it for practical purposes!
For a very detailed analysis of this algorithm, see the paper by H. Gruber, M. Holzer and O. Ruepp titled “Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms“.
Following is a C# implementation, which generates a random array, runs bogosort and then prints some nice statistics:

using System;
namespace Bogosort
{
class Program
{
private static System.Random rnd = new System.Random();
private static int compctr = 0;
static void Main(string[] args)
{
int[] array = GenRandomArray(6);
Console.WriteLine("Sorting a list of " + array.Length + " random numbers between 0 and " + 10 * array.Length + ".");
Console.Write("Original array: ");
PrintArray(array);
int i = 0;
System.DateTime startTime = System.DateTime.Now;
while (!Sorted(array))
{
array = Shuffle(array);
Console.Write("Shuffle " + i + ": ");
PrintArray(array);
i++;
}
System.DateTime stopTime = System.DateTime.Now;
Console.Write("The sorted array is: ");
PrintArray(array);
Console.WriteLine("This required " + i + " shufflings and took " + (stopTime-startTime).Milliseconds + " milliseconds.");
Console.WriteLine("The total number of comparisons made was " + compctr + ", which is " + (double)compctr / (double)i + " comparisons on average.");
Console.WriteLine("The total number of swaps made was " + array.Length * i + ".");
}
private static int Factorial(int x)
{
if (x < 2) return 1;
return x * Factorial(x - 1);
}
private static void PrintArray(int[] array)
{
string s = "";
for (int i =0; i {
s += array[i] + ", ";
}
Console.WriteLine(s + array[array.Length - 1]);
}
private static int[] GenRandomArray(int length)
{
int[] array = new int[length];
for (int i = 0; i < length; i++)
{
array[i] = rnd.Next(10*length);
}
return array;
}
private static bool Sorted(int[] array)
{
for (int i = 1; i < array.Length; i++)
{
compctr++;
if (array[i] < array[i - 1]) return false;
}
return true;
}
private static int[] Shuffle(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
int pos = rnd.Next(array.Length);
int temp = array[pos];
array[pos] = array[i];
array[i] = temp;
}
return array;
}
}
}

For a far better reading experience see the Algorithm wiki page on bogosort.

Here is a great Turing machine simulator (Java applet):
Turing Machine Simulator. You can load predefined programs, including busy beavers, or why not create your own program?

Vad sägs om en härledning som visar att efterföljaren till 0 är 1?
Givet har vi funktionen Succ:
Succ := (λwyx.y(wyx))
och heltalet 0:
0 := (λsz.z),
och vi ska visa att Succ 0 = 1:
S0 = (λwyx.y(wyx)) (λsz.z) = λyx.y((λsz.z)yx) = λyx.yx = 1.
Steg för steg:
Vi utgår från S0 = (λwyx.y(wyx)) (λsz.z):
1. Vi ska ‘beräkna’ funktionen, så vi använder substitution. w i funktionen ersätts med 0, dvs (λsz.z), vi får då kvar λyx.y((λsz.z)yx).
2. Nu appliceras den inre funktionen på y. Alla s ska ersättas med y, men det finns inga s i funktionskroppen, så kvar får vi λyx.y((λz.z)x).
3. Den kvarvarande inre funktionen är förståss identitetsfunktionen, applicerad på x, och vi får λyx.yx som är 1.

Hur ser additionsfunktionen ut i λ-kalkylen?
Tidigare definierade jag tal som upprepad funktionssammansättning, och med det som hjälp är det inte så svårt att definiera addition. Vad behöver vi göra?
För att addera m till n räknar vi först upp till m, och sedan till n. Vi söker alltså den m+n:te sammansättningen av en funktion.
Additionen skriver vi så här:
λm n f x . n f (m f x)
Här är m och n talen vi vill addera, och f är vår sen tidigare kända uppräkningsfunktion, med argumentet x.

Det kan man fråga sig.
Lambda-kalkylen är Turingmaskinens funktionella motsvarighet. Till skillnad från en TM har λ inget tillstånd, utan endast funktionabstraktion och applikation. Det som är fascinerande är att λ är lika kraftfull som en TM.

En snabb introduktion
Observera att detta bara är en snabb intro som förutsätter att man använt sig av lambdafunktioner t.ex. i Haskell. Jag går inte in på formella detaljer här, utan listar bara några grundidéer informellt.
λx.x definierar identitetsfunktionen anonymt. Den tar ett x och ger tillbaka samma x.
Vill vi nu använda vår funktion måste vi skriva ut den (den är ju anonym), så här:
(λx.x) b applicerar funktionen på argumentet b, vilket i detta fall innebär att x byts ut mot b.
Substitution brukar allmänt skrivas E[V := E'], vilket innebär ersättning av variabeln V med E’ där den är fri i E.
Det finns en regel som uttrycker funktionsanvändning, kallad β-reduktion, som ser ut som följer:
β-reduktionen av ((λ V. E) E′) är E[V := E′]. Detta uttrycker den intuitiva substitutionsprincipen.

Tal kan definieras som följer:
0 := λ f x. x
1 := λ f x. f x
2 := λ f x. f (f x)
…
Man kan tänka sig detta som en högre ordningens funktion med två argument, där man upprepade gånger applicerar det ena argumentet på det andra, alltså åstadkommer man något slags uppräkning. Man kan nu definiera ’succ’ och ‘pred’ funktioner, och på den vägen är det.

Fortsättning följer…

Här finns en trevlig algoritmlåt. Bra att lyssna på när man sitter och pluggar till datalogitentor!

Just brilliant!

Stanford har ett arkiv med videomaterial med Donald Knuth !
Titta in här!

Rekursion: se Rekursion…

Listen to this amazing episode of Futures in Biotech!
A talk with professor Larry Smarr on the future of computing, the internet, and science!

I’d like to post some thoughts about one particular problem I face very often. This time I’d like to take it from a more abstract point of view than usually, because I think the generality of this problem is impressive.
Given any sort of structure, it is possible to present it in many different ways. Consider for example a two-dimensional structure like a 2D-graph, drawn on paper vs. represented in a computer’s memory.
Of particular interest to me is representing multi-dimensional structures with fewer (hopefully one) dimensions. Take the case of mathematical notation vs. computer math notation, for instance.
Quite often it is the case that we know multiple ways of representing our structure, but that we lose some information in the process. In our graph example, we wouldn’t know as easily by reading the computer’s memory that the graph represented an octagon, for instance.
Are there transformations that can map all the information from a structure (even information belonging to the original structure) to another, different structure? Probably not. In some sense, the answer is yes though, because we can construct the original graph out of a linear description in a computer’s memory, so the information of the original structure must exist in the linear description as well. However, there is clearly something missing from our linear description. What is going on here?

A bit more mathematically, we can ask whether there exists certain kinds of isomorphisms (in the sense of preserving essential information) between structures?
Wikipedia has some examples of “everyday” isomorphisms, but they do not work for my problem. The first example (with the decks of cards) makes me think “what if the colour is an essential piece of information?” Then these structures are not isomorphic in the sense I use here. Now let us look at the second example, in which we compare a wristwatch to a clock tower. In a way they are isomorphic, but not in my sense of the word. Looking at a wristwatch does not help you understand how a clocktower looks at all, so it is a different kind of isomorphism. This information is stored in the structure, and is not preserved in this case.

But of course… these fail because I used a very bad word in my definition of isomorphism; “essential” information.
We can not exclude any information, for it might be essential for someone or for some purposes.
What is useless to someone might as well be essential for someone else, so that leads us back to my first question, of whether there exists isomorphisms between different structures that preserve ALL information.

Please prove me wrong on this one!

Lustigt nog tror jag faktiskt att denna episod av Math Factor kan ha med det problem jag nyligen beskrev att göra. De frågar egentligen hur många permutationer det finns av n element, och detta med vissa restriktioner på hur man får arrangera dem. Det visar sig att med n=7 får man fler än med n=8… primtal? kanske det!

…närmare bestämt ringen Z_n, se här.
Jag har börjat skriva lite på detta. Jag vill som vanligt utforska så mycket själv, eftersom det ger mest. En tanke jag fick är att detta kan ha någon koppling till ett teorem jag läst so msäger att denna ring är en kropp om och endast om n är ett primtal. Jag är dock inte så bra på att bevisa sådanahär saker, men jag tror beviset kan vara nyttigt. Kanske dags att dyka ner i Discrete and Combinatorial Mathematics: An applied Introduction igen.

Idag kom jag att tänka på något som jag ska titta närmare på när jag har tid. Jag skriver ner det här så jag inte glömmer bort det.
Betrakta en funktion f(x) över ringen Z mod n. Vad avgör om sekvensen f(1), f(2),…, f(n) eventuellt kommer ge alla talen i ringen, eller alltid missa några?