Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory,sci.logic Subject: Re: How Partial Simulations correctly determine non-halting ---Mike Terry Error Date: Tue, 4 Jun 2024 20:33:01 -0500 Organization: A noiseless patient Spider Lines: 30 Message-ID: References: <87h6eamkgf.fsf@bsb.me.uk> <_gWdnbwuZPJP2sL7nZ2dnZfqn_GdnZ2d@brightview.co.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Wed, 05 Jun 2024 03:33:02 +0200 (CEST) Injection-Info: dont-email.me; posting-host="dbcb5a2e000d59c1dda264f94a647a93"; logging-data="707445"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+azpxfGqnnmQp3YswV5RqR" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:9VNmiHqG0zYN5DyAULsOU4hin+g= In-Reply-To: Content-Language: en-US Bytes: 2518 On 6/4/2024 8:20 PM, John Smith wrote: > On 4/06/24 20:02, olcott wrote: >> Those words are dead obviously correct about how a partial simulation >> does correctly determine the halt status of this function: >> >> void Infinite_Recursion2(u32 N) >> { >>      H(Infinite_Recursion2, (ptr)N); >> } > > Does Infinite_Recursion2 halt? When halting is defined in the software engineering terms of terminating normally then Infinite_Recursion2 does not even halt when it runs out of stack space and crashes. *Tail Recursion* Tail recursion is a recursion of a function where it does not consumes stack space and hence prevents stack overflow. If the recursive function is made tail-recursive then it is more efficient than a non-tail- recursive function because every function call does not need to go on stack and pop when the call is done. And it prevents the ugly stack overflow. https://vijeshsalian.medium.com/recursion-how-to-overflow-the-stack-and-how-not-to-b9dcffdfab27 -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer