Fruitbox

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?

Ännu en podcast / netcast / audcast / … att rekommendera: The Math Factor.
Nytt avsnitt (och nytt problem att lösa) varje vecka!

So tomorrow I got an exam in discrete mathematics, good luck to me!
Remember that, there is just one word, that is the key to success in mathematics: PLAGIARIZE!!!
And after that exam, I start a course that will contain, among other things, a lot of programming. So one might get Debugging Angst. The trick here is to take it easy, and break down the problem. Modular Decomposition
Thanks to Eric Siegel! I have always liked the idea of songs about science and such.

Cut-the-knot har en mycket trevlig artikel om bevis. I denna används en liten ordlek som jag finner mycket intressant. Artikeln tar dock inte upp en fråga som jag tycker är intressant, nämligen vad är det minsta antalet ord (steg) som behövs för att transformera ett givet ord till ett annat?
Om man tänker efter lite inser man att detta är ett problem för grafteori. Om vi definierar en graf där noderna är ord, och de är sammanbundna med “vägar”, som är de ord som skiljer sig åt från det ursprungliga ordet med en bokstav. Frågan jag ställde blir nu väsentligen ett enkelt och väl utslitet problem inom grafteorin: att hitta den kortaste vägen i en graf.
Man skulle kunna låta en maskin lösa detta, men då måste den först indexera alla tänkbara ord så att de får denna multidimensionella ordning.

Jag såg något på Mathforge som hittills har undgått mig. Det gäller en artikel om ett nyligen “upptäckt” koncept som upphovsmannen Anderson kallar för transreell aritmetik. Detta är visst en aritmetik på den utökade tallinjen, plus ett nummer till, “nullity”. Axiomatisering och mer återfinns genom Wikipedias artikel om “nullity”.
I denna aritmetik är 0/0 väldefinierat, “nullity”.
Nackdelen är dock att man förlorar vissa mycket trevliga egenskaper som våran vanliga aritmetik har, som till exempel att de transreella talen inte bildar någon Abelsk (kommutativ) grupp under addition (G, +).