Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-10-28 15:46:46

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"

Offline

#2 2009-10-29 20:10:01

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.

Offline

#3 2009-10-30 03:22:03

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... smile

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"

Offline

#4 2009-10-30 05:39:46

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.

Offline

Board footer

Powered by FluxBB