Nathan

Technology hobbyist based in Ithaca, NY

Blog

THE LAMBDA CALCULUS AND GROUP THEORY

Aug 22, 2023

I've been really getting into the lambda calculus, as you can probably tell by my last post. I want to do some research in this field, and I know a thing or two about group theory so I thought I could try to combine them in some way. Very briefly, group theory studies groups, which are like generalized symmetries. A group is a set (usually symmetries) and an operation (usually something like composition). This operation is required to be associative. By combining elements of the group with the operation, you should never be able to get something that isn't another element. There also must be an identity element where operating it with another element doesn't change it, and for each element there has to be an inverse element that gets you back to the identity. If your interested in learning about why this is useful, there are lots of resources available online.

I'm wondering if there is some link between the lambda calculus and group theory. As far as I know, there isn't anything readily available online about this, so this is potentially new territory. If you've watched the video in my previous post, you might notice two almost-examples of groups in the lambda calculus: the Church booleans and Church numerals. Booleans are kind of like the integers mod 1, which is a cyclic group under addition mod 1. I have figured out that addition mod 1 can be represented as xor, and I found an encoding for it. The integers form an infinite group under addition, but the church numerals can only represent natural numbers. There is an encoding integers and integer addition available on the wikipedia article for the Church encoding, so you can form infinite groups with the lambda calculus. But these examples are very special. If you're given a set of any random lambda expressions, it almost certainly does not form a group under any operation. So what is it about the encodings for booleans and integers that make them groups? This is what I'm going to try to figure out.

This has led me to the classification of finite simple groups, in which mathematicians have prooved all finite simple groups are members of just a few infinite families plus some others. Any finite group can be decomposed into simple groups, so they act kind of like prime numbers. If there is a way to represent all of these finite simple groups, then every finite group can be encoded in the lambda calculus. I already developed an encoding for any cyclic group, one of the infinite families, but the others are significantly more complex, and I don't understand them that well. But why is this interesting? Right now, I don't really know. I'm hoping to find some special property of certain lambda expressions that means they will form a group.

The biggest barrier is that lambda expressions, like normal functions, are definitely not associative. It might be useful to research some families of associative functions first, or this project might lead me to find some of those. Another possibiliy may be in combinator calculi. Combinator calculi can encode any lambda expression in just a few combinators. An example is the SKI combinator calculus, which can encode any lambda expression in just 3 combinators. I've messed around with combining these into graphs that have some interesting properties, but they're definitely not associative so that might go in a completely different direction.

-

THE LAMBDA CALCULUS

Aug 18, 2023

If you've used any functional programming languages like Haskell, you might know that they are based off of what's called the lambda calculus. The lambda calculus is a logical system only made up of function definitions and applications. It may suprise you to learn that this system can accomplish anything other languages can. How can that be? You'll have to watch the video to find out.

-

Projects

Media

tau

How To Do Anything With Functions | The Church - Turing Thesis

tau

Why Tau Should be Used in Place of Pi as the Circle Constant

douglass

Self Expression Through Mathematics

matrix

Matrix Inverses and Determinants

Contacts

github

@NathanBirkett

gmail

nb22@icsd.k12.ny.us

discord

printerdpaper

youtube

PrinterdPaper

Skills

html/css/js

The only experience I have is making this website

Java & OOP

I have used java since 2020, and I concider myself intermediate

Python

I have used Python in numerous projects

Kotlin & Android

I made an android app that you can see in the Projects section

GitHub

I am proficient with github and can work with a team

Minecraft mods & datapacks

I haven't made any serious mods but I have experience with forge and datapacks

Classes

Math

Algebra 1, H Geometry, Advanced H Algebra 2 BC, Advanced H Precalculus BC, AP Computer Science A, (AP Calculus BC, Math Seminar)

Science

H Earth Science, H Biology, H Chemistry, AP Chemistry, (AP Physics C)

Technology

H Design and Drawing for Production, H Computer Integrated Manufacturing, H Principles of Engineering

German

H German 1, H German 2, H German 3

History

H Global History 1, H Global History 2, AP US History, (Participation in Government, H Economics)

Music

Concert Band, Wind Ensemble (2 years)

English

H English 9, H English 10, H English 11, (English Digital Media)

Physical Education

PE 9 Fall/Spring, PE 10 Fall/Spring, PE 11 Fall/Spring (PE 12 Fall/Spring, Health Education)

Hobbies

Computer Science

I obviously have an interest in programming, and I am looking forward to learning more about computer science concepts

Robotics

I have been programming head since 2022

Oboe

I have played oboe in school bands since 2016 and got an A on a level 5 Nyssma solo, and am a double reeds section leader

Math

I have always found math exiting and my fields of interest are always shifting

Video Games

My favorites are Minecraft, Scrap Mechanic, and Don't Starve

Anime

Death Note, Jujutsu Kaisen and Vinland Saga are the best animes fight me

Geography

I memorized every country in the world, along with the flags and capitals

Vietnamese

I am attempting to learn Vietnamese for a school trip to Vietnam next February