Math Is Fun Forum

goteamusa

Member

Registered: 2009-10-28

Posts: 7

Busy Beaver Functions

I have read a little about busy beaver functions, but I do not really understand how they work. I know it has to do with the number of steps Turing machines will run until they halt, but I do not understand where the answers come from!? What calculations are being performed? Also, why do the numbers grow so large so quickly? Can this be explained so that it is easy to understand? Thanks.

---

Let us then be up and doing, with a heart for any fate, still achieving still pursuing, learn to labor and to wait.
~Longfellow from "A Psalm of Life"

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Busy Beaver Functions

Hi goteamusa;

I was reading this;

http://en.wikipedia.org/wiki/Busy_beaver

The machine has a 5 tuple of states and 1 halt state. He didn't make it clear to me how the halt state is reached. Also I have always hated the Knuth notation but there really isn't a good notation for a power tower.

The calculations depend apparently on the ackermann function  which is the fastest increasing function known because it is a power tower. This is why they are so large. He cites:

By contrast:

Tiny by comparison!

Last edited by bobbym (2009-10-29 20:16:40)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

goteamusa

Member

Registered: 2009-10-28

Posts: 7

Re: Busy Beaver Functions

Thanks. Actually, I already read that, and I still do not fully understand. That is alright though. Thanks for trying - it was just a whim to understand that - it is not important. I am going to research it a little more on my own and see what happens...

Last edited by goteamusa (2009-10-30 03:22:25)

---

Let us then be up and doing, with a heart for any fate, still achieving still pursuing, learn to labor and to wait.
~Longfellow from "A Psalm of Life"

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Busy Beaver Functions

Hi goteamusa;

I didn't get parts of it either.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.