You are not logged in.
Pages: 1
Define βB(x,y) as BB(x) but restricted to an input size of y.For infinite y,it is uncomputable,otherwise the halting problem would be solvable by simulation.
For finite y,it is computable by brute force.It is monotonic with respect to y(if x>y,βB(n,x)>βB(n,y))
Define Bβ(x) as the smallest y which βB(x,y)=BB(x).It is finite for finite x.(because βB is monotonic,and has to start at 0 and get to BB(x) at infinity,and it can't change from BB(x)-1 to BB(x) at infinity-1(because you can't have infinity-1))It is uncomputable too,since by computing it we can find a non finite upper bound of βB,to replace the uncomputableness of βB(x,inf)
So yeah,two new interesting functions,of one is uncomputable(i found those functions when trying to induce a contradiction in BB(x)(using brute force,but forgot that the tape is infinite,thus proving that βB is computable at finite y)
Where should I submit them?Were them discovered before by other people?
What should they be called?(i called the βB function the busy little beaver function and the Bβ function the unbusy beaver function)
Offline
Pages: 1