Deutsch   English   Français   Italiano  
<a022b87645dc31ff9c810dd3d8d76675b811885e@i2pn2.org>

View for Bookmarking (what is this?)
Look up another Usenet article

Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: joes <noreply@example.org>
Newsgroups: comp.theory
Subject: Re: Correcting the definition of the halting problem --- Computable
 functions
Date: Tue, 25 Mar 2025 08:54:24 -0000 (UTC)
Organization: i2pn2 (i2pn.org)
Message-ID: <a022b87645dc31ff9c810dd3d8d76675b811885e@i2pn2.org>
References: <vr1shq$1qopn$1@dont-email.me> <vr7lbe$2o5t3$1@dont-email.me>
	<vr8p32$3pf1l$1@dont-email.me> <vr9elt$bv13$2@dont-email.me>
	<vr9jpt$gave$2@dont-email.me> <vr9lj6$j0f0$2@dont-email.me>
	<vr9qu8$m4cu$2@dont-email.me> <vr9ttl$q57o$1@dont-email.me>
	<vr9u5m$q57o$2@dont-email.me> <vrbckn$23f4t$1@dont-email.me>
	<vrbtiq$2j07c$2@dont-email.me> <vrc3ud$2p461$1@dont-email.me>
	<vrc4nu$2m36k$5@dont-email.me> <vrkc2m$24ft6$1@dont-email.me>
	<vrkdij$25f9f$3@dont-email.me> <vrlt36$3haib$1@dont-email.me>
	<vrn237$im1e$1@dont-email.me> <vrn67b$md49$1@dont-email.me>
	<cb974817db8e02049daa5604d725300154e33ad1@i2pn2.org>
	<vrps14$35a4m$2@dont-email.me>
	<eab11e8806c669d296bff986870bdc6abdbb2fef@i2pn2.org>
	<vrqicu$3s258$1@dont-email.me>
	<30c2beae6c191f2502e93972a69c85ff227bfd03@i2pn2.org>
	<vrrs79$11a56$7@dont-email.me> <vrrsta$tdm5$1@dont-email.me>
	<vrs264$1a43i$1@dont-email.me> <vrs54q$1d1o2$1@dont-email.me>
	<vrse90$1jr8u$1@dont-email.me> <vrsk13$1q39o$1@dont-email.me>
	<vrsn62$1rblu$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 25 Mar 2025 08:54:24 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="1657017"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="nS1KMHaUuWOnF/ukOJzx6Ssd8y16q9UPs1GZ+I3D0CM";
User-Agent: Pan/0.145 (Duplicitous mercenary valetism; d7e168a
 git.gnome.org/pan2)
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 6317
Lines: 91

Am Mon, 24 Mar 2025 17:43:14 -0500 schrieb olcott:
> On 3/24/2025 4:49 PM, André G. Isaak wrote:
>> On 2025-03-24 14:11, olcott wrote:
>>> On 3/24/2025 12:35 PM, dbush wrote:
>>>> On 3/24/2025 12:44 PM, olcott wrote:
>>>>> On 3/24/2025 10:14 AM, dbush wrote:
>>>>>> On 3/24/2025 11:03 AM, olcott wrote:
>>>>>>> On 3/24/2025 6:23 AM, Richard Damon wrote:
>>>>>>>> On 3/23/25 11:09 PM, olcott wrote:

>>>>>>>>> It is impossible for HHH compute the function from the direct
>>>>>>>>> execution of DDD because DDD is not the finite string input
>>>>>>>>> basis from which all computations must begin.
>>>>>>>>> https://en.wikipedia.org/wiki/Computable_function
>>>>>>>> WHy isn't DDD made into the correct finite string?i
>>>>>>> DDD is a semantically and syntactically correct finite stirng of
>>>>>>> the x86 machine language.
>>>>>> Which includes the machine code of DDD, the machine code of HHH,
>>>>>> and the machine code of everything it calls down to the OS level.
>>>>>>
>>>>>>
>>>>>>>> That seems to be your own fault.
>>>>>>>> The problem has always been that you want to use the wrong string
>>>>>>>> for DDD by excluding the code for HHH from it.
>>>>>>> DDD emulated by HHH directly causes recursive emulation because it
>>>>>>> calls HHH(DDD) to emulate itself again. HHH complies until HHH
>>>>>>> determines that this cycle cannot possibly reach the final halt
>>>>>>> state of DDD.
>>>>>> Which is another way of saying that HHH can't determine that DDD
>>>>>> halts when executed directly.
>>>>> given an input of the function domain it can return the
>>>>> corresponding output.
>>>>> Computable functions are only allowed to compute the mapping from
>>>>> their input finite strings to an output.
>>>> The HHH you implemented is computing *a* computable function, but
>>>> it's not computing the halting function:
>>> The whole point of this post is to prove that no Turing machine ever
>>> reports on the behavior of the direct execution of another Turing
>>> machine.
UTMs do.

>>>> Given any algorithm (i.e. a fixed immutable sequence of instructions)
>>>> X described as <X> with input Y:
>>>> A solution to the halting problem is an algorithm H that computes the
>>>> following mapping:
>>>> (<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
>>> Cannot possibly be a computable function because computable functions
>>> cannot possibly have directly executing Turing machines as their
>>> inputs.
Whatever. It can still compute the direct execution from the description,
which is exactly what the described machine would do.

>> 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.
> 
>> 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.
> 
>> You really need to learn the difference between a Halt decider and the
>> halting function. They are distinct things.
> A halting function need not be a decider?
No, *the* halting function is undecidable.

> In any case no computable function within any model of computation
> computes the mapping from the behavior of any other directly executing
> process to anything else.
Simulators compute the mapping from a description to the directly
executed behaviour. That is computable.

> *THIS MAKES THE FOLLOWING STATEMENT INCORRECT*
> On 3/24/2025 12:35 PM, dbush wrote:
>  > A solution to the halting problem is an algorithm H that computes the
>  > following mapping:
>  > (<X>,Y) maps to 1 if and only if X(Y)
>  > halts when executed directly
>  > (<X>,Y) maps to 0 if and only if X(Y)
>  > does not halt when executed directly
> A definition can be shown to be incorrect when it contradicts other
> definitions in the same system.
And what does it contradict?

-- 
Am Sat, 20 Jul 2024 12:35:31 +0000 schrieb WM in sci.math:
It is not guaranteed that n+1 exists for every n.