Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Fri, 16 May 2025 12:10:09 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <9285f3cd79def14bf4b9bd63c071abaad4acbc3d@i2pn2.org>
References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com>
 <1002akp$2i4bk$2@dont-email.me>
 <479eebef3bd93e82c8fe363908b254b11d15a799.camel@gmail.com>
 <1002jkk$2k00a$3@dont-email.me>
 <05e306f20fcb7c88c497e353aaecd36b30fc752a.camel@gmail.com>
 <10053hb$3759k$1@dont-email.me> <10055rn$37m1t$1@dont-email.me>
 <0e800ac26a88cee27ea427998d53c9e5427b530c.camel@gmail.com>
 <1005k2r$3akrk$2@dont-email.me> <1006pnk$3lfep$1@dont-email.me>
 <1007me6$3qb7l$18@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 16 May 2025 16:11:01 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="619670"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <1007me6$3qb7l$18@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0

On 5/16/25 11:43 AM, olcott wrote:
> On 5/16/2025 2:33 AM, Mikko wrote:
>> On 2025-05-15 20:50:34 +0000, olcott said:
>>
>>> On 5/15/2025 2:57 PM, wij wrote:
>>>> On Thu, 2025-05-15 at 11:47 -0500, olcott wrote:
>>>>> On 5/15/2025 11:08 AM, Mike Terry wrote:
>>>>>> On 14/05/2025 18:53, wij wrote:
>>>>>>> On Wed, 2025-05-14 at 12:24 -0500, olcott wrote:
>>>>>>>> On 5/14/2025 11:43 AM, wij wrote:
>>>>>>>>> On Wed, 2025-05-14 at 09:51 -0500, olcott wrote:
>>>>>>>>>> On 5/14/2025 12:13 AM, wij wrote:
>>>>>>>>>>> Q: Write a turing machine that performs D function (which calls
>>>>>>>>>>> itself):
>>>>>>>>>>>
>>>>>>>>>>> void D() {
>>>>>>>>>>>     D();
>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>> Easy?
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> That is not a TM.
>>>>>>>>>
>>>>>>>>> It is a C program that exists. Therefore, there must be a 
>>>>>>>>> equivalent
>>>>>>>>> TM.
>>>>>>>>>
>>>>>>>>>> To make a TM that references itself the closest
>>>>>>>>>> thing is a UTM that simulates its own TM source-code.
>>>>>>>>>
>>>>>>>>> How does a UTM simulate its own TM source-code?
>>>>>>>>>
>>>>>>>>
>>>>>>>> You run a UTM that has its own source-code on its tape.
>>>>>>>
>>>>>>> What is exactly the source-code on its tape?
>>>>>>>
>>>>>>
>>>>>> Every UTM has some scheme which can be applied to a (TM & input tape)
>>>>>> that is to be simulated.  The scheme says how to turn the (TM + input
>>>>>> tape) into a string of symbols that represent that computation.
>>>>>>
>>>>>> So to answer your question, the "source-code on its tape" is the 
>>>>>> result
>>>>>> of applying the UTM's particular scheme to the combination (UTM, 
>>>>>> input
>>>>>> tape) that is to be simulated.
>>>>>>
>>>>>> If you're looking for the exact string symbols, obviously you 
>>>>>> would need
>>>>>> to specify the exact UTM being used, because every UTM will have a
>>>>>> different answer to your question.
>>>>>>
>>>>>>
>>>>>> Mike.
>>>>>>
>>>>>
>>>>> These things cannot be investigated in great
>>>>> depth because there is no fully encoded UTM in
>>>>> any standard language.
>>>>
>>>> Sort of.
>>>>
>>>>> If there was such a UTM then examining things
>>>>> like a termination analyzer would be too difficult
>>>>> because of the volume of details. Even moving a
>>>>> single value to a specific memory location can
>>>>> take many many steps.
>>>>
>>>> So, which part of POOH is "fully encoded UTM"
>>>>
>>>>> A RASP machine
>>>>> https://en.wikipedia.org/wiki/Random-access_stored-program_machine
>>>>> is a much better fit for examining the details of any
>>>>> complex algorithm.
>>>>>
>>>>> The x86 language is essentially the same thing as a RASP
>>>>> machine for all computations that can be accomplished
>>>>> with the amount of memory that is available.
>>>>
>>>> Absolutely false. POOH is the example that rejected TM/RASP instead 
>>>> of C.
>>>>
>>>> In trying making P!=NP proof (may have defects, I just leave it 
>>>> there to improve)
>>>> https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof- 
>>>> en.txt/download
>>>> I feel TM would be very long and tedious, so I claimed that no 
>>>> *algorithm* can
>>>> solve NPC (algorithmic) problems. (thanks to olcott, this proof was 
>>>> inspired in
>>>> refuting POOH.)
>>>>
>>>> See also Spu in my recent post. TM is very low-level to solve many 
>>>> idea of problems.
>>>>
>>>>> To be a computable function within a model of computation
>>>>> a sequence of the steps of a specific algorithm must be
>>>>> applied to (an often finite string) input to derive an output.
>>>>> https://en.wikipedia.org/wiki/Computable_function
>>>>>
>>>>> When computing the sum() function the steps of the algorithm
>>>>> of arithmetic must be applied to the inputs.
>>>>>
>>>>> *When computing the halt() function steps with a simulating*
>>>>> *termination analyzer the behavioral steps specified by the*
>>>>> *input must be simulated according to the computer language*
>>>>> *of this input*
>>>>>
>>>>> *I may be wrong yet it seems to me that*
>>>>> Computer science never knew these things before in that
>>>>> it never placed any limit on the type of algorithm that
>>>>> must be performed.
>>>>>
>>>>> I think that it was Ben that said that one of two
>>>>> functions that do nothing besides return true or false
>>>>> is correct on all of the counter-example inputs
>>>>> to the halting problem.
>>>>>
>>>>> When we require that a mapping be computed from an
>>>>> input, then this idea is rejected.
>>>>>
>>>>
>>>> You are excellent in quoting tautology to support your claims.
>>>>
>>>
>>> Most people don't know that a mapping must be
>>> computed from the inputs, hence Ben's mistake.
>>
>> Most people don't even know what mappings are. Most people don't
>> make mistakes just because they don't know what mappings are.
>>
>> Ben does not make mistakes just because most people don't know
>> something that Ben does know.
>>
> 
> Ben was wrong when he said that there are a
> pair of computable functions such that one
> of them always gets the correct halt status
> decision. IGNORING THE INPUTS IT NOT ALLOWED
> 

Who says?

suppose I am asked to create a program that computes the difference 
between a natural number and itself.

int selfdiff(int x);

Would it not be correct to just write:

int selfdiff(int  x) { return 0; }

Since the difference between a number and itself is always 0.

Just like a function that given two numbers, compute the sum of 2 + 3

WHCH WAS THE PROBLEM YOU STATED, write a program to compute sum(2, 3)

can be writen as int sum5(int x, int y) { return 5; }, as the input 
values are not needed to compute the result.

The method used to reach the answer is irrelvent in computation theory, 
as long is it is a finite deterministic algorithm working on nothing but 
its defined input. If it can get the right answer ignoring some of its 
inputs, that is fine, and just shows that the mapping it is computing 
wasn't dependent on that input.