Sign in to follow this  
laeuchli

Question about turing machines and busy beavers

Recommended Posts

laeuchli    338
First, moderators, I did cross post this in the lounge last night, but no one seems to know the answer. Also I realize its not directly about game programming. If you feel its inappropriate, please remove it, but I am very curious to know the answer, and don't know another good place to post this. Anyway, I was reading that if one could find S(n) for some sufficiently large number of n, then one could prove various difficult mathematical problems, by showing that a turing machine seeking counter examples will never terminate(and hence there will be no counter examples, and the theorem is proven). However I read that S(n) is thus far only known for n<=5, with only lower bounds established for S(6). Is the problem that there is no universal 5 state two symbol turing machine? This is confusing to me, because didn't they recently prove that there was a 2 state three symbol universal machine? And isn't there also a theorem that you can swap symbols for states? (I may be way off on that,as the class I took on the subject was awhile ago). If so it'd seem possible to construct a turing machine that could be used to prove some of these mathematical theories(although maybe not in a realistic amount of time, which I suppose could be the reason people don't do it, but that was not what was implied by the article). If anyone could clear this up for me I'd appreciate it. Regards, Jesse [Edited by - laeuchli on February 29, 2008 2:07:36 PM]

Share this post


Link to post
Share on other sites
FluxCapacitor    200
I'm not an expert on the subject by any means, and I'm not entirely sure what you're asking, but one easy way to show that the busy beaver function is non-computable is to (by construction) show that the halting problem can be reduced to it. I don't think finding a 2-symbol universal turing machine with a given number of states would help at all, because the busy beaver machine has to start with a blank tape (thus the UTM is reduced to a single-function TM like any other.) And yes, the winner of the recent NKS prize proved the existence of a 2 state, 3 symbol UTM, but IIRC there is no algorithm in general to swap symbols for states (if there was, you could swap all of your symbols for states and end up with a finite state machine.)

[Edited by - FluxCapacitor on February 29, 2008 1:17:36 PM]

Share this post


Link to post
Share on other sites
laeuchli    338
I certainly understand that Busy Beaver functions are non-computable, but that doesnt rule out finding them, as indeed people have done.

The article I read on wikipedia claimed a 20-30 state machine would be sufficant but is currently implausible. I guess what I'm asking, is how can you tell what number N is needed for an N-state two symbol turning machine to be able to compute something useful. I suppose by 5 states you can tell by exhustive examination that nothing intresting can be built(although some of the outputs produced by 5 state machines are massivly complex and take billions of cycles to halt), although I'm confused then how a 2 state 3 symbol machine can be so much more powerful?

Share this post


Link to post
Share on other sites
FluxCapacitor    200
The 2 state, 3 symbol machine only produces complex output if it's given complex input (e.g. another Turing Machine). In the busy beaver problem, where you're restricted to an empty input, a TM with 5 states could certainly beat the 2 state machine.

Share this post


Link to post
Share on other sites
laeuchli    338
So how can you decide what n-state machine you'd need to produce useful output? As I said the wikipedia article claimed 20+ for something like goldbach's conjecture.

[Edited by - laeuchli on February 29, 2008 5:02:35 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this