Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #104683

Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry]

Cross-posted to 2 groups.

Show all headers | View raw

On 5/11/24 12:06 PM, olcott wrote:
> On 5/11/2024 3:00 AM, Mikko wrote:
>> On 2024-05-10 18:16:37 +0000, olcott said:
>>
>>> On 3/1/2024 12:41 PM, Mike Terry wrote:
>>
>>>> Obviously a simulator has access to the internal state (tape 
>>>> contents etc.) of the simulated machine.  No problem there.
>>>>
>>>> What isn't allowed is the simulated machine altering its own 
>>>> behaviour by accessing data outside of its own state.  (I.e. 
>>>> accessing data from its parent simulators state.)
>>>>
>>>> While an "active-simulator" [my own term] is at liberty to combine
>>>> straight simulation with add-on "enhancements" that extend the
>>>> functionality of the simulated machine, in doing so it would no
>>>> longer be a simulator in the sense you need it to be.  So you
>>>> mustn't do this!
>>
>> In principle an incorrect simulation is permissible. However, to prove
>> that the result inferred from an incorrect simulation is correct may
>> be impossible.
>>
> 
> Within the conventional terms-of-the-art of {termination analyzer}
> and {simulator} an incorrect simulation is forbidden.


 From what definitions.

I would say that based on the definition of simulation that you imply 
you are using (by the using of it to bridge from the behavior of the 
program to the simlulation of the program) ALL your H that answer about 
D have used an "incorrect" simulation.

> 
>>> *You did not provide complete reasoning justifying this proclamation*
>>> *You did not provide complete reasoning justifying this proclamation*
>>> *You did not provide complete reasoning justifying this proclamation*
>>
>> The provided reasoning is sufficient. You can continue reasoning from
>> that if you want more.
>>
> 
> *He is SIMPLY WRONG and when he tries*
> *to justify what he said he will fail*
> 
> Any pure x86 emulator or UTM can have the added functionality
> of watching every state change of its simulated input without
> changing the simulated steps of this input relative to an
> unmodified x86 emulator or UTM.
> 
> *SO MIKE TERRY IS SIMPLY WRONG ABOUT THIS*
> 
>>> Because the simulator must perform every detail of the simulation of
>>> the underlying machine it can watch every single state change of this
>>> underlying machine and this does not change the behavior of the
>>> simulated input AT ALL (relative to not watching the state changes).
>>
>> Yes, that is a correct interpretation.
>>
> 
> OK Great!
> So a simulating termination analyzer could watch the behavior of its
> input and analyze this watched behavior and transition to a non-final
> state that indicates non-halting and then go back and continue
> simulating the non-halting input and it remains a simulator all along.

HOw can you "return" the non-halting indication and then continue to run?

> 
> *This would not be a halt decider because all deciders must halt*
> *It would be an unconventional termination analyzer*

It wouldn't be a program by the normal definitions of a program.

> 
> *It does correctly report that its pathological input never halts*

Nope.

> 
> *This method does work correctly on the H/D template*
> *and the Ĥ applied to ⟨Ĥ⟩ template shown below*
> 
> 00 int H(ptr x, ptr x)  // ptr is pointer to int function
> 01 int D(ptr x)
> 02 {
> 03   int Halt_Status = H(x, x);
> 04   if (Halt_Status)
> 05     HERE: goto HERE;
> 06   return Halt_Status;
> 07 }
> 08
> 09 int main()
> 10 {
> 11   H(D,D);
> 12 }
> 
> When Ĥ is applied to ⟨Ĥ⟩
> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> 
> *Termination Analyzer H is Not Fooled by Pathological Input D*
> https://www.researchgate.net/publication/369971402_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
> 

Nope, because the H you just described is not equivalent to a Turing 
Machine.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] olcott <polcott333@gmail.com> - 2024-05-10 13:16 -0500
  Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Mikko <mikko.levanto@iki.fi> - 2024-05-11 11:00 +0300
    Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] olcott <polcott333@gmail.com> - 2024-05-11 11:06 -0500
      Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2024-05-11 17:32 +0100
        Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry](apology) olcott <polcott333@gmail.com> - 2024-05-11 12:04 -0500
      Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Richard Damon <richard@damon-family.org> - 2024-05-11 12:46 -0400
        Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] olcott <polcott333@gmail.com> - 2024-05-11 12:19 -0500
          Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] olcott <polcott333@gmail.com> - 2024-05-11 15:16 -0500
            Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Richard Damon <richard@damon-family.org> - 2024-05-11 19:24 -0400
          Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Richard Damon <richard@damon-family.org> - 2024-05-11 19:25 -0400
      Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] olcott <polcott333@gmail.com> - 2024-05-12 09:18 -0500
        Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Mikko <mikko.levanto@iki.fi> - 2024-05-12 18:14 +0300
          Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] olcott <polcott333@gmail.com> - 2024-05-12 11:53 -0500
            Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Richard Damon <richard@damon-family.org> - 2024-05-12 13:07 -0400
            Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Mikko <mikko.levanto@iki.fi> - 2024-05-13 11:09 +0300
        Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry] Richard Damon <richard@damon-family.org> - 2024-05-12 12:57 -0400

csiph-web