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)
By the input size, do you mean the size of the tape for the Turing Machine? (sorry if this is a stupid question, I don't know much theoretical CS)
If that's what you mean I don't think it matches up with the original definition since Turing Machines are supposed to have infinite memory (i.e. infinite tape length)
I couldn't find any references to these functions online, but I simply may not be looking hard enough.
You said that you wanted to "submit" these functions. (I'm going to assume that by that you mean that you want to publish them somewhere.) It's probably possible to submit this to a math journal, but you would probably have to find some sort of practical use for these functions, and make sure that your claims about them are supported by a valid mathematical proof. It would probably be more difficult than if you were actually at a university, but it's probably possible.
Umm only if the machine halts for all inputs with length ≤ y.
I'm not convinced. Suppose your Turing machine is programmed to compute, I dunno, n! for odd values of n, 0 for even n, where n is the input length. Then βB(x,n) is monotonic if you look only at odd n, but goes down to some small constant for even n.
I'm not sure I understand this, but it seems like you're proving that all functions are finite for finite x, or at least all monotonic functions. How about f(x)=אₙ? If there's any meaning to an infinite argument to a function, it has to be the limit as n➞∞ of f(finite n), and that doesn't lead to a need of "infinity-1".
The definition of BB says that it excludes non halting stuff...
(I think that you mean programmed to run for x steps,not programmed to compute x)
You cannot get the input length,because the tape is infinite,and you cannot be 100% sure there are no inputs ahead even if passing TREE(3) zeros right?
nah im not proving that for all functions,just for that function i was talking about
I am saying,that if you know that as y increases,βB(x,y) starts at 0 and ends at BB(x),so it either has some finite point which it already equals BB(x) or has some infinite point when it does that.But there is only one (countable) infinity(or only one infinity smaller or equal to Ω0 which is the infinity it gets to BB(x))so it either never gets to BB(x)(which is not true) or it gets to BB(x) at some finite point.
Yes, but when you say "brute force" I take it to mean that you try every possible input, because you don't know in advance whether this function will run forever on this input.
What I'm saying is that there's no such thing as "ends at" when you're talking about functions of infinity. There are only limits of sequences, and that's perfectly calculable even that there's no "value at ∞-1," or for that matter, no value at ∞. There are only limits.
Yes. But then you can't make an argument about infinity minus 1, because the limit mechanism makes sense of sort-of behavior at infinity entirely by using functions of finite arguments.
well I wanted to mean that a monotonic function that has domain N and codomain {x:xEN,0<=x<=some finite integer},and limit as x goes to infinity it goes to that finite integer,then it has to have some finite point when it reaches that finite integer
if its codomain spanned the reals,it wouldn't be true
if it does not start at 0 or end at a finite number it wouldn't be true
Oh! Yes, that sounds right. I was thinking of real functions; the whole idea of a limit of integer functions seems strange to me. Limits are all about continuity! But yes, for your purposes this is fine.