On 4/18/25 3:00 PM, Mr Flibble wrote:
Flibble's Law:
If a problem permits infinite behavior in its formulation, it permits
infinite analysis of that behavior in its decidability scope.
Why?
Especially when the question is "Is the behavior of the process
infinite?"
The issue is that fundamentally, knowledge must be based on finite
processes, as we can't do infinite analysis and do anything with the
answer.
Knowing that a process will be infinite, allows us to not waste all of
our time on something that won't get us an answer.
The basic result of all this sort of proof, is that there are cases
where we can't ever know for certain if we are on a wild-goose-chase
that will never give a result, or we are on a path that WILL give a
result eventually if we persist long enough.
Knowing that there ARE Wild-Goose-Chases as fundamental properties of
systems lets us plan better for what to do.
We KNOW we can't be perfect in all we do, so we accept realistic
results, and try to keep improving.
On Fri, 18 Apr 2025 15:08:55 -0400, Richard Damon wrote:
On 4/18/25 3:00 PM, Mr Flibble wrote:
Flibble's Law:
If a problem permits infinite behavior in its formulation, it permits
infinite analysis of that behavior in its decidability scope.
Why?
Especially when the question is "Is the behavior of the process
infinite?"
The issue is that fundamentally, knowledge must be based on finite
processes, as we can't do infinite analysis and do anything with the
answer.
Knowing that a process will be infinite, allows us to not waste all of
our time on something that won't get us an answer.
The basic result of all this sort of proof, is that there are cases
where we can't ever know for certain if we are on a wild-goose-chase
that will never give a result, or we are on a path that WILL give a
result eventually if we persist long enough.
Knowing that there ARE Wild-Goose-Chases as fundamental properties of
systems lets us plan better for what to do.
We KNOW we can't be perfect in all we do, so we accept realistic
results, and try to keep improving.
It is about playing the game by the rules of the game:
If Busy Beavers are allowed an INFINITE tape in the context of the Halting Problem then Simulating Halt Deciders are allowed INFINITE resources.
/Flibble
Flibble's Law:
If a problem permits infinite behavior in its formulation, it permits infinite analysis of that behavior in its decidability scope.
On 4/18/25 5:01 PM, Mr Flibble wrote:
On Fri, 18 Apr 2025 15:08:55 -0400, Richard Damon wrote:
On 4/18/25 3:00 PM, Mr Flibble wrote:
Flibble's Law:
If a problem permits infinite behavior in its formulation, it permits
infinite analysis of that behavior in its decidability scope.
Why?
Especially when the question is "Is the behavior of the process
infinite?"
The issue is that fundamentally, knowledge must be based on finite
processes, as we can't do infinite analysis and do anything with the
answer.
Knowing that a process will be infinite, allows us to not waste all of
our time on something that won't get us an answer.
The basic result of all this sort of proof, is that there are cases
where we can't ever know for certain if we are on a wild-goose-chase
that will never give a result, or we are on a path that WILL give a
result eventually if we persist long enough.
Knowing that there ARE Wild-Goose-Chases as fundamental properties of
systems lets us plan better for what to do.
We KNOW we can't be perfect in all we do, so we accept realistic
results, and try to keep improving.
It is about playing the game by the rules of the game:
Right, and the rules of the game say deciders must answer in finite time
or they aren't deciders.
Possible inputs might be programs that do not halt, but will run
forever, and possible never repeat an exact state, and the decider, to
be a correct decider, must detect this in finite time.
If Busy Beavers are allowed an INFINITE tape in the context of the
Halting Problem then Simulating Halt Deciders are allowed INFINITE
resources.
/Flibble
Sure, they can use as much tape as they want, they just can't use
infinite time.
Note, Busy-Beaver is about detecting if a program IS a busy beaver, some possible inputs will be non-halting with infinite growth, and these need
to be rejected, and rejected in finite time.
On Fri, 18 Apr 2025 17:13:23 -0400, Richard Damon wrote:
On 4/18/25 5:01 PM, Mr Flibble wrote:
On Fri, 18 Apr 2025 15:08:55 -0400, Richard Damon wrote:
On 4/18/25 3:00 PM, Mr Flibble wrote:
Flibble's Law:
If a problem permits infinite behavior in its formulation, it permits >>>>> infinite analysis of that behavior in its decidability scope.
Why?
Especially when the question is "Is the behavior of the process
infinite?"
The issue is that fundamentally, knowledge must be based on finite
processes, as we can't do infinite analysis and do anything with the
answer.
Knowing that a process will be infinite, allows us to not waste all of >>>> our time on something that won't get us an answer.
The basic result of all this sort of proof, is that there are cases
where we can't ever know for certain if we are on a wild-goose-chase
that will never give a result, or we are on a path that WILL give a
result eventually if we persist long enough.
Knowing that there ARE Wild-Goose-Chases as fundamental properties of
systems lets us plan better for what to do.
We KNOW we can't be perfect in all we do, so we accept realistic
results, and try to keep improving.
It is about playing the game by the rules of the game:
Right, and the rules of the game say deciders must answer in finite time
or they aren't deciders.
Possible inputs might be programs that do not halt, but will run
forever, and possible never repeat an exact state, and the decider, to
be a correct decider, must detect this in finite time.
If Busy Beavers are allowed an INFINITE tape in the context of the
Halting Problem then Simulating Halt Deciders are allowed INFINITE
resources.
/Flibble
Sure, they can use as much tape as they want, they just can't use
infinite time.
Note, Busy-Beaver is about detecting if a program IS a busy beaver, some
possible inputs will be non-halting with infinite growth, and these need
to be rejected, and rejected in finite time.
I'm not claiming we can build a decider with infinite resources.
I'm saying that if the problem permits infinite machines, then infinite analyzers are fair game in theory.
The Flibble Reciprocity Principle:
In theoretical computation, every permitted infinity in problem
formulation implies a permitted infinity in problem analysis.
It's about playing the game by the rules of the game.
/Flibble
Richard Damon <richard@damon-family.org> writes:
On 4/18/25 5:16 PM, Mr Flibble wrote:[...]
I'm not claiming we can build a decider with infinite resources.
I'm saying that if the problem permits infinite machines, then
infinite analyzers are fair game in theory.
No, you don't get to say that.
Well, actually ...
Sure, Mr. Flibble gets to say anything he likes. Anyone can
define a mathematical system with any consistent rules they like,
and derive results that apply within that system.
The Flibble Reciprocity Principle:
In theoretical computation, every permitted infinity in problem
formulation implies a permitted infinity in problem analysis.
It's about playing the game by the rules of the game.
No, it is making up your own rules and admittion that you think
cheating is ok.
The "Rules" exist, and are defined, and they say that decider do NOT
get infinite time.
The "Rules" are fundamentally arbitrary (but ideally chosen for
their relevance to the real world). Defining a new set of rules
is how we got useful and/or interesting things like non-Euclidean
geometry and complex numbers.
The flaw in Flibble's reasoning is that he claims that some kind of
"fair game" principle implies that he can make certain specific
rule changes. I suggest that he doesn't need that excuse.
The rules under which most of us operate, and in which the Halting
Problem proof was constructed, are designed to correspond to
real-world computational models (with some simplifications like
not limiting storage size).
Mr. Flibble, I think, is inventing new rules because he doesn't like
the results from the existing rules. I think he dislikes the fact
that the Halting Problem is not solvable, and is trying to define a
new system in which it's solvable in some sense. And sure, he can
(try to) do that if he likes. But it's worth spending time on that
*only* if the results of the new rules are interesting and/or useful.
It's also a good thing if the new rules are clearly defined, for
example rigorously defining what a "pathological input" is.
It would also be nice if Mr. Flibble acknowledged that the proof of
the unsolvability of the Halting Problem is valid within the usual
set of rules (and that he understands those rules), rather than
implying that the proof is invalid because the rules are "unfair"
or something.
Richard Damon <richard@damon-family.org> writes:
On 4/18/25 5:16 PM, Mr Flibble wrote:[...]
I'm not claiming we can build a decider with infinite resources.
I'm saying that if the problem permits infinite machines, then
infinite analyzers are fair game in theory.
No, you don't get to say that.
Well, actually ...
Sure, Mr. Flibble gets to say anything he likes. Anyone can
define a mathematical system with any consistent rules they like,
and derive results that apply within that system.
The Flibble Reciprocity Principle:
In theoretical computation, every permitted infinity in problem
formulation implies a permitted infinity in problem analysis.
It's about playing the game by the rules of the game.
No, it is making up your own rules and admittion that you think
cheating is ok.
The "Rules" exist, and are defined, and they say that decider do NOT
get infinite time.
The "Rules" are fundamentally arbitrary (but ideally chosen for
their relevance to the real world). Defining a new set of rules
is how we got useful and/or interesting things like non-Euclidean
geometry and complex numbers.
The flaw in Flibble's reasoning is that he claims that some kind of
"fair game" principle implies that he can make certain specific
rule changes. I suggest that he doesn't need that excuse.
The rules under which most of us operate, and in which the Halting
Problem proof was constructed, are designed to correspond to
real-world computational models (with some simplifications like
not limiting storage size).
Mr. Flibble, I think, is inventing new rules because he doesn't like
the results from the existing rules. I think he dislikes the fact
that the Halting Problem is not solvable, and is trying to define a
new system in which it's solvable in some sense. And sure, he can
(try to) do that if he likes. But it's worth spending time on that
*only* if the results of the new rules are interesting and/or useful.
It's also a good thing if the new rules are clearly defined, for
example rigorously defining what a "pathological input" is.
It would also be nice if Mr. Flibble acknowledged that the proof of
the unsolvability of the Halting Problem is valid within the usual
set of rules (and that he understands those rules), rather than
implying that the proof is invalid because the rules are "unfair"
or something.
If a problem permits infinite behavior in its formulation, it permits infinite analysis of that behavior in its decidability scope.
On 4/18/2025 8:38 PM, Mike Terry wrote:according to the semantics of the x86 language is proven when exactly
On 19/04/2025 00:19, Keith Thompson wrote:
Richard Damon <richard@damon-family.org> writes:
On 4/18/25 5:16 PM, Mr Flibble wrote:[...]
I'm not claiming we can build a decider with infinite resources.
I'm saying that if the problem permits infinite machines, then
infinite analyzers are fair game in theory.
No, you don't get to say that.
Well, actually ...
Sure, Mr. Flibble gets to say anything he likes. Anyone can
define a mathematical system with any consistent rules they like,
and derive results that apply within that system.
The Flibble Reciprocity Principle:
In theoretical computation, every permitted infinity in problem
formulation implies a permitted infinity in problem analysis.
It's about playing the game by the rules of the game.
No, it is making up your own rules and admittion that you think
cheating is ok.
The "Rules" exist, and are defined, and they say that decider do NOT
get infinite time.
The "Rules" are fundamentally arbitrary (but ideally chosen for
their relevance to the real world). Defining a new set of rules
is how we got useful and/or interesting things like non-Euclidean
geometry and complex numbers.
The flaw in Flibble's reasoning is that he claims that some kind of
"fair game" principle implies that he can make certain specific
rule changes. I suggest that he doesn't need that excuse.
The rules under which most of us operate, and in which the Halting
Problem proof was constructed, are designed to correspond to
real-world computational models (with some simplifications like
not limiting storage size).
Mr. Flibble, I think, is inventing new rules because he doesn't like
the results from the existing rules. I think he dislikes the fact
that the Halting Problem is not solvable, and is trying to define a
new system in which it's solvable in some sense. And sure, he can
(try to) do that if he likes. But it's worth spending time on that
*only* if the results of the new rules are interesting and/or useful.
It's also a good thing if the new rules are clearly defined, for
example rigorously defining what a "pathological input" is.
It would also be nice if Mr. Flibble acknowledged that the proof of
the unsolvability of the Halting Problem is valid within the usual
set of rules (and that he understands those rules), rather than
implying that the proof is invalid because the rules are "unfair"
or something.
I'm not convinced Mr.Flibble has had a proper shot at understanding
the halting problem as it is properly stated (in mathematics /
computer science). Also I think he is far more sensible than PO, when
it comes to understanding what's being said in an argument, although
also it has to be said that's a very low bar...
I suspect Mr.Flibble's only visibility of HP has come via a
combination of C.Strachey's "An impossible program" article, and PO
threads on these newsgroups! He might be forgiven for getting the
wrong impression over issues of self reference etc., and he freely
admitted on his first PO- thread posting that he was quite new to HP.
Unlike PO, I'm pretty sure he has actually changed his opinion about
something(?) once he understood the background better. PO has no
prospect of ever undertanding the background of anything technical
like HP.
So a great thing for Mr.Fibble to do would be to forget everything in
Strachey's correspondence and everything that PO has said on these
As I remember is Flibble first heard of the Halting Problem
from me and that was probably my Strachey Link.
https://academic.oup.com/comjnl/article-abstract/7/4/313/354243? redirectedFrom=fulltext
newsgroups about "pathelogical self reference" etc., and go back to
reading e.g. Linz's HP proof to understand what HP says and the proof
in particular. PO has extracted the half a dozen or so pages from the
Linz proof into a PDF which he has published somewhere, probably on
ResearchGate. [I'm sure I could find this if PO doesn't chip in with
details]
https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf
If Mr.Flibble went back to a proper HP problem statement he might
hopefully realise that the "pathelogical" self-reference is not of a
type that is of any concern, due to the order things are done in the
proper HP proof. It is no different from the kind of self reference
we see e.g. in a backup utility backing up its own source code, or
even backing up its own executable file.
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
*The input to HHH(DD) specifies recursive emulation*
Lying about this or changing the subject to a different
instance of than DD emulated by HHH using will be
ridiculed as dishonest or stupid.
That the finite string given to HHH specifies a halting program
On 4/18/2025 8:38 PM, Mike Terry wrote:
On 19/04/2025 00:19, Keith Thompson wrote:
Richard Damon <richard@damon-family.org> writes:
On 4/18/25 5:16 PM, Mr Flibble wrote:[...]
I'm not claiming we can build a decider with infinite resources.
I'm saying that if the problem permits infinite machines, then
infinite analyzers are fair game in theory.
No, you don't get to say that.
Well, actually ...
Sure, Mr. Flibble gets to say anything he likes. Anyone can
define a mathematical system with any consistent rules they like,
and derive results that apply within that system.
The Flibble Reciprocity Principle:
In theoretical computation, every permitted infinity in problem
formulation implies a permitted infinity in problem analysis.
It's about playing the game by the rules of the game.
No, it is making up your own rules and admittion that you think
cheating is ok.
The "Rules" exist, and are defined, and they say that decider do NOT
get infinite time.
The "Rules" are fundamentally arbitrary (but ideally chosen for
their relevance to the real world). Defining a new set of rules
is how we got useful and/or interesting things like non-Euclidean
geometry and complex numbers.
The flaw in Flibble's reasoning is that he claims that some kind of
"fair game" principle implies that he can make certain specific
rule changes. I suggest that he doesn't need that excuse.
The rules under which most of us operate, and in which the Halting
Problem proof was constructed, are designed to correspond to
real-world computational models (with some simplifications like
not limiting storage size).
Mr. Flibble, I think, is inventing new rules because he doesn't like
the results from the existing rules. I think he dislikes the fact
that the Halting Problem is not solvable, and is trying to define a
new system in which it's solvable in some sense. And sure, he can
(try to) do that if he likes. But it's worth spending time on that
*only* if the results of the new rules are interesting and/or useful.
It's also a good thing if the new rules are clearly defined, for
example rigorously defining what a "pathological input" is.
It would also be nice if Mr. Flibble acknowledged that the proof of
the unsolvability of the Halting Problem is valid within the usual
set of rules (and that he understands those rules), rather than
implying that the proof is invalid because the rules are "unfair"
or something.
I'm not convinced Mr.Flibble has had a proper shot at understanding
the halting problem as it is properly stated (in mathematics /
computer science). Also I think he is far more sensible than PO, when
it comes to understanding what's being said in an argument, although
also it has to be said that's a very low bar...
I suspect Mr.Flibble's only visibility of HP has come via a
combination of C.Strachey's "An impossible program" article, and PO
threads on these newsgroups! He might be forgiven for getting the
wrong impression over issues of self reference etc., and he freely
admitted on his first PO- thread posting that he was quite new to HP.
Unlike PO, I'm pretty sure he has actually changed his opinion about
something(?) once he understood the background better. PO has no
prospect of ever undertanding the background of anything technical
like HP.
So a great thing for Mr.Fibble to do would be to forget everything in
Strachey's correspondence and everything that PO has said on these
As I remember is Flibble first heard of the Halting Problem
from me and that was probably my Strachey Link.
https://academic.oup.com/comjnl/article-abstract/7/4/313/354243? redirectedFrom=fulltext
newsgroups about "pathelogical self reference" etc., and go back to
reading e.g. Linz's HP proof to understand what HP says and the proof
in particular. PO has extracted the half a dozen or so pages from the
Linz proof into a PDF which he has published somewhere, probably on
ResearchGate. [I'm sure I could find this if PO doesn't chip in with
details]
https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf
If Mr.Flibble went back to a proper HP problem statement he might
hopefully realise that the "pathelogical" self-reference is not of a
type that is of any concern, due to the order things are done in the
proper HP proof. It is no different from the kind of self reference
we see e.g. in a backup utility backing up its own source code, or
even backing up its own executable file.
int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}
*The input to HHH(DD) specifies recursive emulation*
Lying about this or changing the subject to a different
instance of than DD emulated by HHH using will be
ridiculed as dishonest or stupid.
I doubt Mr.Flibble would be worried by this if he understood the
situation! In particular there is no "category error" anywhere in the
proper statement and proof of HP, due to the careful order things are
defined.
His term "category error" is perfectly apt and
a key new insight very important to the problem.
Professor Hehner and I use different terms for
this same idea.
Then again, maybe he would understand it all as little as PO
understands it! But I would give him at least a chance at properly
understanding rather than basing his views on PO threads + Strachey
correspondence. :)
----------------
Regarding this thread and "Flibble's law" - you are right that there
is no "fair game" law. People just make up a variety of rules and
analyse/ discuss the consequences. That applies to HP as much as
anything else.
Except there really is such a thing as objective truth.
[Also I don't know what Mr.Flibble means by "allowing infinite
resources" to analyse halting. He might just mean "TMs have an
infinite tape, so TM analysers should be allowed a similar infinite
tape". That is indeed what is allowed, as analysers are taken to be
TMs. Or he might mean analysers should be allowed infinite time - but
what would that actually mean?? Anyway, but the point of my post is
that I'm not sure Mr.Flibble has given himself a fair shot at
understanding HP, not to comment on this thread particularly.]
Regards,
Mike.
On 4/18/25 5:01 PM, Mr Flibble wrote:
If Busy Beavers are allowed an INFINITE tape in the context of the
Halting Problem then Simulating Halt Deciders are allowed INFINITE
resources.
/Flibble
Sure, they can use as much tape as they want, they just can't use
infinite time.
On Fri, 18 Apr 2025 17:13:23 -0400, Richard Damon wrote:
On 4/18/25 5:01 PM, Mr Flibble wrote:
If Busy Beavers are allowed an INFINITE tape in the context of the
Halting Problem then Simulating Halt Deciders are allowed INFINITE
resources.
/Flibble
Sure, they can use as much tape as they want, they just can't use
infinite time.
If they REQUIRE infinite tape then by implication they REQUIRE infinite
time.
/Flibble
On 4/22/2025 5:35 PM, Keith Thompson wrote:
Mr Flibble <flibble@red-dwarf.jmc.corp> writes:
On Fri, 18 Apr 2025 17:13:23 -0400, Richard Damon wrote:
On 4/18/25 5:01 PM, Mr Flibble wrote:
If Busy Beavers are allowed an INFINITE tape in the context of the
Halting Problem then Simulating Halt Deciders are allowed INFINITE
resources.
Sure, they can use as much tape as they want, they just can't use
infinite time.
If they REQUIRE infinite tape then by implication they REQUIRE infinite
time.
But they don't REQUIRE (does all-caps really help?) either infinite
tape or infinite time. Unless I've misunderstood the concept, a Busy
Beaver by definition must terminate after a finite number of steps.
We sometimes say "infinite tape" as a verbal shorthand for "as much
tape as is required". Or we can say that infinite tape exists,
but we'll never use more than a finite amount of it. The amount of
tape required is never actually infinite, but there is no specific
upper bound.
(I sometimes wonder if we don't distinguish clearly enough between
"unbounded" and "infinite".)
That is an important nuance that many people miss.
There are actual (mathematically describable, not physically
implementable) Turing machines that consume infinite time and
infinite tape. Busy Beavers do not.
Busy Beaver seems to quickly consume much more
memory than there are atoms in the universe.
Richard Damon <richard@damon-family.org> writes:
[...]
Actual Busy Beavers, since they do halt, never actually require
infinite tape.
Perspective Busy Beavers, which might not halt, are allowed to use
infinite tape, and the decider will need to figure out that they
aren't going to halt to know they are not a Busy Beaver.
I think you mean "Prospective", not "Perspective". (For a moment I
thought there might be some concept of a "Perspective Busy Beaver",
perhaps one that operates in the Total Perspective Vortex.)
Note, I never said that the Busy Beaver NEEDED the infinite tape, but
there is no finite bound on the tape they are allowed to use, but if
they are a Busy Beaver, it will be finite.
Richard Damon <richard@damon-family.org> writes:
[...]
Yes, there is a nuance, but there ARE some processes that aren't just
unbounded by go infinite. Unbounded can only reach countable infinity,
but not uncountable infinity. Thus a process that was performing the
super-task of writing out all the real numbers between 0 and 1 would
use TRULY infinite tape (needing at least Aleph-1 cells) and infinite
time to complete.
Hmm. It seems to me that that would be beyond the scope of any
Turing machine.
A trivial Turing machine could write out an unending sequence of
1s to its tape, never halting. Such a machine would need a truly
infinite tape (Aleph-0 cells) if you let it run for an infinite
time. I suppose you could loosely say that it "finishes" its task
of writing infinite 1s after an infinite time. Another TM could
repeatedly write 1s to the same location without moving the tape;
such a machine could be left running for an infinite type but would
only consume finite tape.
I suggest that something that can potentially execute Aleph-1 steps
or consume Aleph-1 tape cells is not a TM.
In the same way, an unbounded process, could be thought of, as
"finishing" after a countable infinite number of steps, while another
process might just never stop as in a countable infinite number of
steps it never reaches its end (because it takes an uncountable
infinite number of steps).
I'd say that a TM that takes a countably infinite number of steps
just never completes (though we can discuss the *limit* of its
output), while a machine that takes an uncountably infinite number
of steps isn't a TM.
Actual experts, please jump in and tell me where I'm wrong.
[...]
On 4/22/25 6:46 PM, olcott wrote:
On 4/22/2025 5:35 PM, Keith Thompson wrote:
Mr Flibble <flibble@red-dwarf.jmc.corp> writes:That is an important nuance that many people miss.
On Fri, 18 Apr 2025 17:13:23 -0400, Richard Damon wrote:
On 4/18/25 5:01 PM, Mr Flibble wrote:
If Busy Beavers are allowed an INFINITE tape in the context of the >>>>>> Halting Problem then Simulating Halt Deciders are allowed INFINITE >>>>>> resources.
Sure, they can use as much tape as they want, they just can't use
infinite time.
If they REQUIRE infinite tape then by implication they REQUIRE
infinite time.
But they don't REQUIRE (does all-caps really help?) either infinite
tape or infinite time. Unless I've misunderstood the concept, a Busy
Beaver by definition must terminate after a finite number of steps.
We sometimes say "infinite tape" as a verbal shorthand for "as much
tape as is required". Or we can say that infinite tape exists,
but we'll never use more than a finite amount of it. The amount of
tape required is never actually infinite, but there is no specific
upper bound.
(I sometimes wonder if we don't distinguish clearly enough between
"unbounded" and "infinite".)
Yes, there is a nuance, but there ARE some processes that aren't just unbounded by go infinite. Unbounded can only reach countable infinity,
but not uncountable infinity. Thus a process that was performing the super-task of writing out all the real numbers between 0 and 1 would use TRULY infinite tape (needing at least Aleph-1 cells) and infinite time
to complete.
In the same way, an unbounded process, could be thought of, as
"finishing" after a countable infinite number of steps, while another
process might just never stop as in a countable infinite number of steps
it never reaches its end (because it takes an uncountable infinite
number of steps).
Some do, but mostly it is the programs pretending to be Busy BeaversThere are actual (mathematically describable, not physicallyBusy Beaver seems to quickly consume much more memory than there are
implementable) Turing machines that consume infinite time and infinite
tape. Busy Beavers do not.
atoms in the universe.
that actually never halt, and thus are not actually Busy Beavers.
On Tue, 22 Apr 2025 22:24:44 -0400, Richard Damon wrote:
On 4/22/25 6:46 PM, olcott wrote:
On 4/22/2025 5:35 PM, Keith Thompson wrote:
Mr Flibble <flibble@red-dwarf.jmc.corp> writes:That is an important nuance that many people miss.
On Fri, 18 Apr 2025 17:13:23 -0400, Richard Damon wrote:
On 4/18/25 5:01 PM, Mr Flibble wrote:
If Busy Beavers are allowed an INFINITE tape in the context of the >>>>>>> Halting Problem then Simulating Halt Deciders are allowed INFINITE >>>>>>> resources.
Sure, they can use as much tape as they want, they just can't use
infinite time.
If they REQUIRE infinite tape then by implication they REQUIRE
infinite time.
But they don't REQUIRE (does all-caps really help?) either infinite
tape or infinite time. Unless I've misunderstood the concept, a Busy >>>> Beaver by definition must terminate after a finite number of steps.
We sometimes say "infinite tape" as a verbal shorthand for "as much
tape as is required". Or we can say that infinite tape exists,
but we'll never use more than a finite amount of it. The amount of
tape required is never actually infinite, but there is no specific
upper bound.
(I sometimes wonder if we don't distinguish clearly enough between
"unbounded" and "infinite".)
Yes, there is a nuance, but there ARE some processes that aren't just
unbounded by go infinite. Unbounded can only reach countable infinity,
but not uncountable infinity. Thus a process that was performing the
super-task of writing out all the real numbers between 0 and 1 would use
TRULY infinite tape (needing at least Aleph-1 cells) and infinite time
to complete.
In the same way, an unbounded process, could be thought of, as
"finishing" after a countable infinite number of steps, while another
process might just never stop as in a countable infinite number of steps
it never reaches its end (because it takes an uncountable infinite
number of steps).
Some do, but mostly it is the programs pretending to be Busy BeaversThere are actual (mathematically describable, not physicallyBusy Beaver seems to quickly consume much more memory than there are
implementable) Turing machines that consume infinite time and infinite >>>> tape. Busy Beavers do not.
atoms in the universe.
that actually never halt, and thus are not actually Busy Beavers.
You have no clue about what you are talking about: it doesn't matter if
the number of steps is uncountably infinite or countably infinite, it
would still never complete and Flibble's Law still applies.
/Flibble
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 546 |
| Nodes: | 16 (0 / 16) |
| Uptime: | 162:07:21 |
| Calls: | 10,385 |
| Calls today: | 2 |
| Files: | 14,057 |
| Messages: | 6,416,500 |