Re: Unpartial Halt Deciders

Liste des GroupesRevenir à c theory 
Sujet : Re: Unpartial Halt Deciders
De : richard (at) *nospam* damon-family.org (Richard Damon)
Groupes : comp.theory
Date : 18. Apr 2025, 18:37:23
Autres entêtes
Organisation : i2pn2 (i2pn.org)
Message-ID : <e6d2caab68d37e22d7e3a59eaeaf5d21004f148b@i2pn2.org>
References : 1 2 3
User-Agent : Mozilla Thunderbird
On 4/18/25 10:50 AM, Mr Flibble wrote:
On Fri, 18 Apr 2025 10:30:05 -0400, Richard Damon wrote:
 
Does your new definition handle the busy-beaver problem? (Which could be
solved if we actually had halt deciders)
 Yes, because:
 * The Busy Beaver machines being considered “well-formed” (i.e., not
pathological).
So, the other proofs of the Busy-Beaver number being uncomputable don't apply?
 * The ability to detect non-halting via repeated state (which is valid for
Turing machines with bounded state spaces).\
But it isn't, as Turing Machines have an unbounded 'state' space with their tape. They have finite states of the machine, but unbounded state of the tape, so infinite loops using that tape can occur and never repeat "state".

 * Granting infinite resources for simulation.
Yes, it needs unbounded resources, but it still must detected in bounded time, and detecting loops in programs that have been growing in space requirements, via their unbounded tape,

 /Flibble

Date Sujet#  Auteur
18 Apr 25 * Re: Unpartial Halt Deciders2Richard Damon
18 Apr 25 `- Re: Unpartial Halt Deciders1Richard Damon

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal