Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Correcting the definition of the halting problem --- Computable functions Date: Tue, 25 Mar 2025 08:01:14 -0500 Organization: A noiseless patient Spider Lines: 48 Message-ID: References: <30c2beae6c191f2502e93972a69c85ff227bfd03@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 25 Mar 2025 14:01:15 +0100 (CET) Injection-Info: dont-email.me; posting-host="9741c665c88d9215381b06ce738934cb"; logging-data="3432809"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18W72ZxM4xdIxvTF5iJfyli" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:f02Jr4ggO+rBk2gR++UnORS/1yw= X-Antivirus: Norton (VPS 250324-4, 3/24/2025), Outbound message In-Reply-To: Content-Language: en-US X-Antivirus-Status: Clean Bytes: 4619 On 3/25/2025 3:47 AM, joes wrote: > Am Mon, 24 Mar 2025 18:04:21 -0500 schrieb olcott: >> On 3/24/2025 5:49 PM, André G. Isaak wrote: >>> On 2025-03-24 16:43, olcott wrote: >>> >>>>> Computable functions don't have inputs. They have domains. Turing >>>>> machines have inputs. >>>> Maybe when pure math objects. In every model of computation they seem >>>> to always have inputs. >>> Computable functions *are* pure math objects. You seem to want to >>> conflate them with C functions, but that is not the case. >>> The crucial point is that the domains of computable functions are *not* >>> restricted to strings, even if the inputs to Turing Machines are. >>> >>>>> While the inputs to TMs are restricted to strings, there is no such >>>>> such restriction on computable functions. >>>>> The vast majority of computable functions of interest do *not* have >>>>> strings as their domains, yet they remain computable functions (a >>>>> simple example would be the parity function which maps NATURAL >>>>> NUMBERS (not strings) to yes/no values.) >>>> Since there is a bijection between natural numbers and strings of >>>> decimal digits your qualification seems vacuous. >>> There is not a bijection between natural numbers and strings. There is >>> a one-to-many mapping from natural numbers to strings, just as there is >>> a one-to-many mapping from computations (i.e. turing machine/input >>> string pairs, i.e. actual Turing machines directly running on their >>> inputs) to strings. > >> When III is emulated by pure emulator EEE for any finite number of steps >> of emulation according to the semantics of the x86 language it never >> reaches its own "ret" instruction final halt state THUS DOES NOT HALT. >> When III is directly executed calls an EEE instance that only emulates >> finite number of steps then this directly executed III always reaches >> its own "ret" instruction final halt state THUS HALTS. > A pure simulator can not limit the number of steps. Also III doesn't > halt in, say, 3 steps. Why should III call a different instance > that doesn't abort, when it is being simulated? > The fact that the same states in the program-under-test keep repeating such that the program-under-test cannot possibly reach its own final halt state proves that program-under-test does not halt. -- Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer