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


Groups > comp.theory > #40760 > unrolled thread

I finally completed my lexical analyzer generator (needed by my halt decider)

Started byolcott <NoOne@NoWhere.com>
First post2021-10-23 20:27 -0500
Last post2021-10-26 23:47 +0100
Articles 20 on this page of 25 — 4 participants

Back to article view | Back to comp.theory


Contents

  I finally completed my lexical analyzer generator (needed by my halt decider) olcott <NoOne@NoWhere.com> - 2021-10-23 20:27 -0500
    Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-23 21:49 -0400
      Re: I finally completed my lexical analyzer generator (needed by my halt decider) olcott <NoOne@NoWhere.com> - 2021-10-23 21:16 -0500
        Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-23 23:19 -0400
          Re: I finally completed my lexical analyzer generator ( axiomatic basis ) olcott <NoOne@NoWhere.com> - 2021-10-23 22:29 -0500
            Re: I finally completed my lexical analyzer generator ( axiomatic basis ) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 06:40 -0400
              Re: I finally completed my lexical analyzer generator ( axiomatic basis ) olcott <NoOne@NoWhere.com> - 2021-10-24 09:04 -0500
                Re: I finally completed my lexical analyzer generator ( axiomatic basis ) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 13:37 -0400
                  Re: I finally completed my lexical analyzer generator ( semantic tautology ) olcott <NoOne@NoWhere.com> - 2021-10-25 10:02 -0500
                    Re: I finally completed my lexical analyzer generator ( semantic tautology ) Richard Damon <Richard@Damon-Family.org> - 2021-10-25 19:40 -0400
    Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 07:59 -0400
      Re: I finally completed my lexical analyzer generator (needed by my halt decider) olcott <NoOne@NoWhere.com> - 2021-10-24 09:07 -0500
        Re: I finally completed my lexical analyzer generator (needed by my halt decider) Richard Damon <Richard@Damon-Family.org> - 2021-10-24 13:41 -0400
    Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-24 13:37 -0500
      Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Richard Damon <Richard@Damon-Family.org> - 2021-10-24 15:55 -0400
      Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-25 02:08 +0100
        Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-24 20:45 -0500
          Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 00:26 +0100
            Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-25 19:08 -0500
              Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 02:09 +0100
                Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-25 20:54 -0500
                  Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Richard Damon <news.x.richarddamon@xoxy.net> - 2021-10-26 07:00 -0400
                  Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 14:56 +0100
                    Re: I finally completed my lexical analyzer generator (needed by my halt decider) update olcott <NoOne@NoWhere.com> - 2021-10-26 09:43 -0500
                      Re: I finally completed my lexical analyzer generator (needed by my halt decider) update Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-10-26 23:47 +0100

Page 1 of 2  [1] 2  Next page →


#40760 — I finally completed my lexical analyzer generator (needed by my halt decider)

Fromolcott <NoOne@NoWhere.com>
Date2021-10-23 20:27 -0500
SubjectI finally completed my lexical analyzer generator (needed by my halt decider)
Message-ID<TpydnRmO3dkGK-n8nZ2dnUU7-c3NnZ2d@giganews.com>
In order to make my halt decider a pure function it had to have a way to 
look at the inputs to function calls. In order to look at the inputs to 
function calls it had to know how many inputs that a function has.

This is DFA analyzes C source code to provide the number of parameters 
of each function in the file. The number of parameters per function is 
the number of {vt} matches per {fn} match.

The only thing that will change with this file is that the halt decider 
will use different halt deciding criteria so that the halt decider 
becomes a pure function.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 


In computer programming, a pure function is a function that has the 
following properties:[1][2]

(1) The function return values are identical for identical arguments (no 
variation with local static variables, non-local variables, mutable 
reference arguments or input streams).

(2) The function application has no side effects (no mutation of local 
static variables, non-local variables, mutable reference arguments or 
input/output streams).

https://en.wikipedia.org/wiki/Pure_function



//
//  Deterministic Finite Automaton (DFA) recognizer
//  of C function headers.

// Character Classes
//
     EMPTY [0]
     ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
   NUMERIC [0123456789]
        WS [0x09,0x0A,0x0D,0x20]
    LPAREN [(]
    RPAREN [)]
  ASTERISK [*]
     COMMA [,]
   COMMENT [0x2f]
   NEWLINE [0x0A]
     ASCII [0x20-0x7e]
   CONTROL [0x00-0x09,0x0b-0x1f,0x7f]


// Recognized Patterns
//
{et} Empty
{ft} Function_Type
{fn} Function_Name
{vt} Variable_Type
{vn} Variable_Name
{fh} Function_Header

// DFA Definition to recognize C function headers

// begin of function type
<00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
<01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
<02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)

// begin of function name
<03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
<04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
<05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)

// begin of variable type
<06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
<07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
<08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)

// begin of variable name
<09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
<10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
<11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)

// ignores all "//" comments
<12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
<13> CONTROL(13) ASCII(13)  [0x0A] (00)

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [next] | [standalone]


#40761

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-23 21:49 -0400
Message-ID<mY2dJ.3216$k35.2640@fx33.iad>
In reply to#40760
On 10/23/21 9:27 PM, olcott wrote:
> In order to make my halt decider a pure function it had to have a way to 
> look at the inputs to function calls. In order to look at the inputs to 
> function calls it had to know how many inputs that a function has.
> 
> This is DFA analyzes C source code to provide the number of parameters 
> of each function in the file. The number of parameters per function is 
> the number of {vt} matches per {fn} match.
> 
> The only thing that will change with this file is that the halt decider 
> will use different halt deciding criteria so that the halt decider 
> becomes a pure function.
> 
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
> 
> 
> In computer programming, a pure function is a function that has the 
> following properties:[1][2]
> 
> (1) The function return values are identical for identical arguments (no 
> variation with local static variables, non-local variables, mutable 
> reference arguments or input streams).
> 
> (2) The function application has no side effects (no mutation of local 
> static variables, non-local variables, mutable reference arguments or 
> input/output streams).
> 
> https://en.wikipedia.org/wiki/Pure_function
> 
> 
> 
> //
> //  Deterministic Finite Automaton (DFA) recognizer
> //  of C function headers.
> 
> // Character Classes
> //
>      EMPTY [0]
>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>    NUMERIC [0123456789]
>         WS [0x09,0x0A,0x0D,0x20]
>     LPAREN [(]
>     RPAREN [)]
>   ASTERISK [*]
>      COMMA [,]
>    COMMENT [0x2f]
>    NEWLINE [0x0A]
>      ASCII [0x20-0x7e]
>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
> 
> 
> // Recognized Patterns
> //
> {et} Empty
> {ft} Function_Type
> {fn} Function_Name
> {vt} Variable_Type
> {vn} Variable_Name
> {fh} Function_Header
> 
> // DFA Definition to recognize C function headers
> 
> // begin of function type
> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
> 
> // begin of function name
> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
> 
> // begin of variable type
> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
> 
> // begin of variable name
> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
> 
> // ignores all "//" comments
> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
> 

Ok,

Just remember that being a 'Pure Funciton' isn't the actual requirement, 
the decider needs to be a Mathematical Computation, which means that all 
copies of it, when given the same inputs, generates the same outputs.

You STILL have the error that you treat H as a 'pure simulator' when it 
is not, it is only a 'pure simulatior until' and as such, the behavior 
of the copy of H in H^ DOES have an affect on the behavior of that H^. 
Remember, a 'Pure Simulator' (aka a UTM) NEVER stops simulating until 
the machine it is simulating ends, even if that takes forever.

Do you think you are immortal as you will be living until you die?

This effect is easy to actually prove by looking at the trace of the run 
of H^/P when run as a top level mchine, and seeing that the call to H 
inside it does abort its simulation, returns non-halting, and thus H^/P 
does Halt.

If H is actually a Computation, as requried, then ALL copies of it must 
do exactly that same thing.

[toc] | [prev] | [next] | [standalone]


#40762

Fromolcott <NoOne@NoWhere.com>
Date2021-10-23 21:16 -0500
Message-ID<0e2dnU2hms9oXOn8nZ2dnUU7-SXNnZ2d@giganews.com>
In reply to#40761
On 10/23/2021 8:49 PM, Richard Damon wrote:
> 
> On 10/23/21 9:27 PM, olcott wrote:
>> In order to make my halt decider a pure function it had to have a way 
>> to look at the inputs to function calls. In order to look at the 
>> inputs to function calls it had to know how many inputs that a 
>> function has.
>>
>> This is DFA analyzes C source code to provide the number of parameters 
>> of each function in the file. The number of parameters per function is 
>> the number of {vt} matches per {fn} match.
>>
>> The only thing that will change with this file is that the halt 
>> decider will use different halt deciding criteria so that the halt 
>> decider becomes a pure function.
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>
>>
>> In computer programming, a pure function is a function that has the 
>> following properties:[1][2]
>>
>> (1) The function return values are identical for identical arguments 
>> (no variation with local static variables, non-local variables, 
>> mutable reference arguments or input streams).
>>
>> (2) The function application has no side effects (no mutation of local 
>> static variables, non-local variables, mutable reference arguments or 
>> input/output streams).
>>
>> https://en.wikipedia.org/wiki/Pure_function
>>
>>
>>
>> //
>> //  Deterministic Finite Automaton (DFA) recognizer
>> //  of C function headers.
>>
>> // Character Classes
>> //
>>      EMPTY [0]
>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>    NUMERIC [0123456789]
>>         WS [0x09,0x0A,0x0D,0x20]
>>     LPAREN [(]
>>     RPAREN [)]
>>   ASTERISK [*]
>>      COMMA [,]
>>    COMMENT [0x2f]
>>    NEWLINE [0x0A]
>>      ASCII [0x20-0x7e]
>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>
>>
>> // Recognized Patterns
>> //
>> {et} Empty
>> {ft} Function_Type
>> {fn} Function_Name
>> {vt} Variable_Type
>> {vn} Variable_Name
>> {fh} Function_Header
>>
>> // DFA Definition to recognize C function headers
>>
>> // begin of function type
>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>
>> // begin of function name
>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>
>> // begin of variable type
>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>
>> // begin of variable name
>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>
>> // ignores all "//" comments
>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>
> 
> Ok,
> 
> Just remember that being a 'Pure Funciton' isn't the actual requirement, 
> the decider needs to be a Mathematical Computation, which means that all 
> copies of it, when given the same inputs, generates the same outputs.
> 
> You STILL have the error that you treat H as a 'pure simulator' when it 
> is not, it is only a 'pure simulatior until' and as such, the behavior 
> of the copy of H in H^ DOES have an affect on the behavior of that H^. 
> Remember, a 'Pure Simulator' (aka a UTM) NEVER stops simulating until 
> the machine it is simulating ends, even if that takes forever.
> 

void Infinite_Loop()
{
   HERE: goto HERE;
}

_Infinite_Loop()
[00000ab0](01)  55              push ebp
[00000ab1](02)  8bec            mov ebp,esp
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab5](01)  5d              pop ebp
[00000ab6](01)  c3              ret
Size in bytes:(0007) [00000ab6]

Are you saying that the only way that a simulating halt decider can 
correctly decide that the above code will never stop running is to wait 
until the end of time?



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40763

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-23 23:19 -0400
Message-ID<4h4dJ.71260$qe4.24572@fx45.iad>
In reply to#40762
On 10/23/21 10:16 PM, olcott wrote:
> On 10/23/2021 8:49 PM, Richard Damon wrote:
>>
>> On 10/23/21 9:27 PM, olcott wrote:
>>> In order to make my halt decider a pure function it had to have a way 
>>> to look at the inputs to function calls. In order to look at the 
>>> inputs to function calls it had to know how many inputs that a 
>>> function has.
>>>
>>> This is DFA analyzes C source code to provide the number of 
>>> parameters of each function in the file. The number of parameters per 
>>> function is the number of {vt} matches per {fn} match.
>>>
>>> The only thing that will change with this file is that the halt 
>>> decider will use different halt deciding criteria so that the halt 
>>> decider becomes a pure function.
>>>
>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>
>>>
>>> In computer programming, a pure function is a function that has the 
>>> following properties:[1][2]
>>>
>>> (1) The function return values are identical for identical arguments 
>>> (no variation with local static variables, non-local variables, 
>>> mutable reference arguments or input streams).
>>>
>>> (2) The function application has no side effects (no mutation of 
>>> local static variables, non-local variables, mutable reference 
>>> arguments or input/output streams).
>>>
>>> https://en.wikipedia.org/wiki/Pure_function
>>>
>>>
>>>
>>> //
>>> //  Deterministic Finite Automaton (DFA) recognizer
>>> //  of C function headers.
>>>
>>> // Character Classes
>>> //
>>>      EMPTY [0]
>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>    NUMERIC [0123456789]
>>>         WS [0x09,0x0A,0x0D,0x20]
>>>     LPAREN [(]
>>>     RPAREN [)]
>>>   ASTERISK [*]
>>>      COMMA [,]
>>>    COMMENT [0x2f]
>>>    NEWLINE [0x0A]
>>>      ASCII [0x20-0x7e]
>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>
>>>
>>> // Recognized Patterns
>>> //
>>> {et} Empty
>>> {ft} Function_Type
>>> {fn} Function_Name
>>> {vt} Variable_Type
>>> {vn} Variable_Name
>>> {fh} Function_Header
>>>
>>> // DFA Definition to recognize C function headers
>>>
>>> // begin of function type
>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>
>>> // begin of function name
>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>
>>> // begin of variable type
>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>
>>> // begin of variable name
>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>
>>> // ignores all "//" comments
>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>
>>
>> Ok,
>>
>> Just remember that being a 'Pure Funciton' isn't the actual 
>> requirement, the decider needs to be a Mathematical Computation, which 
>> means that all copies of it, when given the same inputs, generates the 
>> same outputs.
>>
>> You STILL have the error that you treat H as a 'pure simulator' when 
>> it is not, it is only a 'pure simulatior until' and as such, the 
>> behavior of the copy of H in H^ DOES have an affect on the behavior of 
>> that H^. Remember, a 'Pure Simulator' (aka a UTM) NEVER stops 
>> simulating until the machine it is simulating ends, even if that takes 
>> forever.
>>
> 
> void Infinite_Loop()
> {
>    HERE: goto HERE;
> }
> 
> _Infinite_Loop()
> [00000ab0](01)  55              push ebp
> [00000ab1](02)  8bec            mov ebp,esp
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab5](01)  5d              pop ebp
> [00000ab6](01)  c3              ret
> Size in bytes:(0007) [00000ab6]
> 
> Are you saying that the only way that a simulating halt decider can 
> correctly decide that the above code will never stop running is to wait 
> until the end of time?
> 

No. You seem to have a reading comprension problem.

The Simulating Halt Decider is fully allowed to abort the simulation of 
the machine it is simulationg.

The only issue is that IF it does so, it can't treat itself as if it was 
a UTM/Pure SImulator, and thus the fact that it never saw the comptation 
reach a halting state isn't proof of anything.

For the above program, that isn't an issue, it can easily see the loop 
without a conditional in it and thus detect that the loop is forever.

The same thing for a 'normal' infinite recursion that doesn't go though 
H, that also is easily detected and aborted.

The problem is the recursion through H, which is NOT an 'infinite' 
recursion for an H that is able to abort its simulation in this case. If 
H can abort, it is NOT a UTM/Pure SImulator, so you can't use the 
transform of converting the simulation of the simulator to the trace of 
the simulated machine. It just doesn't Hold. You also can't 'ignore' the 
presence of the copy of the simulator in the machine it is simulating, 
as that copy DOES affect the behavior of the machine (dispite your false 
rheteric claiming otherwise).

Your H uses UNSOUND logic to decide that H^ is non-halting, which is why 
you come up with a Halting Computation appearing to be non-halting.

You logic conflates the version of your decider that does abort the 
simulation with the totally different version that does not, and the 
totally different version of H^ that uses that other version.

THAT IS JUST WROHG.

[toc] | [prev] | [next] | [standalone]


#40764 — Re: I finally completed my lexical analyzer generator ( axiomatic basis )

Fromolcott <NoOne@NoWhere.com>
Date2021-10-23 22:29 -0500
SubjectRe: I finally completed my lexical analyzer generator ( axiomatic basis )
Message-ID<QJydnYuUluu0Tun8nZ2dnUU7-KvNnZ2d@giganews.com>
In reply to#40763
On 10/23/2021 10:19 PM, Richard Damon wrote:
> On 10/23/21 10:16 PM, olcott wrote:
>> On 10/23/2021 8:49 PM, Richard Damon wrote:
>>>
>>> On 10/23/21 9:27 PM, olcott wrote:
>>>> In order to make my halt decider a pure function it had to have a 
>>>> way to look at the inputs to function calls. In order to look at the 
>>>> inputs to function calls it had to know how many inputs that a 
>>>> function has.
>>>>
>>>> This is DFA analyzes C source code to provide the number of 
>>>> parameters of each function in the file. The number of parameters 
>>>> per function is the number of {vt} matches per {fn} match.
>>>>
>>>> The only thing that will change with this file is that the halt 
>>>> decider will use different halt deciding criteria so that the halt 
>>>> decider becomes a pure function.
>>>>
>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>>
>>>>
>>>> In computer programming, a pure function is a function that has the 
>>>> following properties:[1][2]
>>>>
>>>> (1) The function return values are identical for identical arguments 
>>>> (no variation with local static variables, non-local variables, 
>>>> mutable reference arguments or input streams).
>>>>
>>>> (2) The function application has no side effects (no mutation of 
>>>> local static variables, non-local variables, mutable reference 
>>>> arguments or input/output streams).
>>>>
>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>
>>>>
>>>>
>>>> //
>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>> //  of C function headers.
>>>>
>>>> // Character Classes
>>>> //
>>>>      EMPTY [0]
>>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>    NUMERIC [0123456789]
>>>>         WS [0x09,0x0A,0x0D,0x20]
>>>>     LPAREN [(]
>>>>     RPAREN [)]
>>>>   ASTERISK [*]
>>>>      COMMA [,]
>>>>    COMMENT [0x2f]
>>>>    NEWLINE [0x0A]
>>>>      ASCII [0x20-0x7e]
>>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>
>>>>
>>>> // Recognized Patterns
>>>> //
>>>> {et} Empty
>>>> {ft} Function_Type
>>>> {fn} Function_Name
>>>> {vt} Variable_Type
>>>> {vn} Variable_Name
>>>> {fh} Function_Header
>>>>
>>>> // DFA Definition to recognize C function headers
>>>>
>>>> // begin of function type
>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>
>>>> // begin of function name
>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>
>>>> // begin of variable type
>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>>
>>>> // begin of variable name
>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>
>>>> // ignores all "//" comments
>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>>
>>>
>>> Ok,
>>>
>>> Just remember that being a 'Pure Funciton' isn't the actual 
>>> requirement, the decider needs to be a Mathematical Computation, 
>>> which means that all copies of it, when given the same inputs, 
>>> generates the same outputs.
>>>
>>> You STILL have the error that you treat H as a 'pure simulator' when 
>>> it is not, it is only a 'pure simulatior until' and as such, the 
>>> behavior of the copy of H in H^ DOES have an affect on the behavior 
>>> of that H^. Remember, a 'Pure Simulator' (aka a UTM) NEVER stops 
>>> simulating until the machine it is simulating ends, even if that 
>>> takes forever.
>>>
>>
>> void Infinite_Loop()
>> {
>>    HERE: goto HERE;
>> }
>>
>> _Infinite_Loop()
>> [00000ab0](01)  55              push ebp
>> [00000ab1](02)  8bec            mov ebp,esp
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab5](01)  5d              pop ebp
>> [00000ab6](01)  c3              ret
>> Size in bytes:(0007) [00000ab6]
>>
>> Are you saying that the only way that a simulating halt decider can 
>> correctly decide that the above code will never stop running is to 
>> wait until the end of time?
>>
> 
> No. You seem to have a reading comprension problem.
> 
> The Simulating Halt Decider is fully allowed to abort the simulation of 
> the machine it is simulationg.
> 
> The only issue is that IF it does so, it can't treat itself as if it was 
> a UTM/Pure SImulator, and thus the fact that it never saw the comptation 
> reach a halting state isn't proof of anything.

When a simulating halt decider acts as if it is a pure simulator and 
watches the behavior of an infinite loop it can correctly abort the 
simulation of this input and report that this input never halts. We can 
generalize this simplest case of infinite execution to all other cases:

All that I am doing is generalizing this same idea. When-so-ever a 
simulating halt decider can correctly axiomatically determine that its 
input would never halt if it remained a pure simulator then it can abort 
the simulation of this input and report that this input never halts.

When a simulating halt decider correctly axiomatically determines X then 
we know that X is necessarily true.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40765 — Re: I finally completed my lexical analyzer generator ( axiomatic basis )

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-24 06:40 -0400
SubjectRe: I finally completed my lexical analyzer generator ( axiomatic basis )
Message-ID<FKadJ.9264$Np3.5602@fx06.iad>
In reply to#40764
On 10/23/21 11:29 PM, olcott wrote:
> On 10/23/2021 10:19 PM, Richard Damon wrote:
>> On 10/23/21 10:16 PM, olcott wrote:
>>> On 10/23/2021 8:49 PM, Richard Damon wrote:
>>>>
>>>> On 10/23/21 9:27 PM, olcott wrote:
>>>>> In order to make my halt decider a pure function it had to have a 
>>>>> way to look at the inputs to function calls. In order to look at 
>>>>> the inputs to function calls it had to know how many inputs that a 
>>>>> function has.
>>>>>
>>>>> This is DFA analyzes C source code to provide the number of 
>>>>> parameters of each function in the file. The number of parameters 
>>>>> per function is the number of {vt} matches per {fn} match.
>>>>>
>>>>> The only thing that will change with this file is that the halt 
>>>>> decider will use different halt deciding criteria so that the halt 
>>>>> decider becomes a pure function.
>>>>>
>>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>>>
>>>>>
>>>>> In computer programming, a pure function is a function that has the 
>>>>> following properties:[1][2]
>>>>>
>>>>> (1) The function return values are identical for identical 
>>>>> arguments (no variation with local static variables, non-local 
>>>>> variables, mutable reference arguments or input streams).
>>>>>
>>>>> (2) The function application has no side effects (no mutation of 
>>>>> local static variables, non-local variables, mutable reference 
>>>>> arguments or input/output streams).
>>>>>
>>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>>
>>>>>
>>>>>
>>>>> //
>>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>>> //  of C function headers.
>>>>>
>>>>> // Character Classes
>>>>> //
>>>>>      EMPTY [0]
>>>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>>    NUMERIC [0123456789]
>>>>>         WS [0x09,0x0A,0x0D,0x20]
>>>>>     LPAREN [(]
>>>>>     RPAREN [)]
>>>>>   ASTERISK [*]
>>>>>      COMMA [,]
>>>>>    COMMENT [0x2f]
>>>>>    NEWLINE [0x0A]
>>>>>      ASCII [0x20-0x7e]
>>>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>>
>>>>>
>>>>> // Recognized Patterns
>>>>> //
>>>>> {et} Empty
>>>>> {ft} Function_Type
>>>>> {fn} Function_Name
>>>>> {vt} Variable_Type
>>>>> {vn} Variable_Name
>>>>> {fh} Function_Header
>>>>>
>>>>> // DFA Definition to recognize C function headers
>>>>>
>>>>> // begin of function type
>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>>
>>>>> // begin of function name
>>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>>
>>>>> // begin of variable type
>>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>>>
>>>>> // begin of variable name
>>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>>
>>>>> // ignores all "//" comments
>>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>>>
>>>>
>>>> Ok,
>>>>
>>>> Just remember that being a 'Pure Funciton' isn't the actual 
>>>> requirement, the decider needs to be a Mathematical Computation, 
>>>> which means that all copies of it, when given the same inputs, 
>>>> generates the same outputs.
>>>>
>>>> You STILL have the error that you treat H as a 'pure simulator' when 
>>>> it is not, it is only a 'pure simulatior until' and as such, the 
>>>> behavior of the copy of H in H^ DOES have an affect on the behavior 
>>>> of that H^. Remember, a 'Pure Simulator' (aka a UTM) NEVER stops 
>>>> simulating until the machine it is simulating ends, even if that 
>>>> takes forever.
>>>>
>>>
>>> void Infinite_Loop()
>>> {
>>>    HERE: goto HERE;
>>> }
>>>
>>> _Infinite_Loop()
>>> [00000ab0](01)  55              push ebp
>>> [00000ab1](02)  8bec            mov ebp,esp
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab5](01)  5d              pop ebp
>>> [00000ab6](01)  c3              ret
>>> Size in bytes:(0007) [00000ab6]
>>>
>>> Are you saying that the only way that a simulating halt decider can 
>>> correctly decide that the above code will never stop running is to 
>>> wait until the end of time?
>>>
>>
>> No. You seem to have a reading comprension problem.
>>
>> The Simulating Halt Decider is fully allowed to abort the simulation 
>> of the machine it is simulationg.
>>
>> The only issue is that IF it does so, it can't treat itself as if it 
>> was a UTM/Pure SImulator, and thus the fact that it never saw the 
>> comptation reach a halting state isn't proof of anything.
> 
> When a simulating halt decider acts as if it is a pure simulator and 
> watches the behavior of an infinite loop it can correctly abort the 
> simulation of this input and report that this input never halts. We can 
> generalize this simplest case of infinite execution to all other cases:
> 
> All that I am doing is generalizing this same idea. When-so-ever a 
> simulating halt decider can correctly axiomatically determine that its 
> input would never halt if it remained a pure simulator then it can abort 
> the simulation of this input and report that this input never halts.
> 
> When a simulating halt decider correctly axiomatically determines X then 
> we know that X is necessarily true.
> 
> 

NO!

You are making an INCORRECT generalization. It is just like claiming 
that log(a+b+c) is log(a) + log(b) + log(c) because we have the case 
that log(1+2+3) = log(1) + log(2) + log(3).

You have made a claim, PROVE IT. Not just a rhetorical argument done 
with vague words, but an honest to god actual analytical proof, using 
the exact same accepted definitions of all the words. And then go and 
prove that setup does meet the conditions required by the proof to use it.

You say 'axiomatically', but that is just YOUR DISHONEST DOGDE to insert 
in a statement that is FALSE.

Now, part of the problem is that you make a number of small errors that 
you continue to just ignore and these build up to your false conclusion.

Your statement would be correct if pronoun usage was correct and the 
usage refered to just this one COPY being adjusted, and not the shared 
copy being changed, which causes the change to change the supposed to be 
fixed algorithm employed by the input being simulated. We know that for 
THAT case, H is incorrect, as using an ACTUAL 'Pure Simulator' to 
process this input (where H^ still uses the original H that does abort) 
shows that H^ WILL HALT, and thus the claim "would not halt unless H 
aborts the simulation" is incorrect.

These errors have been pointed out to you repeatedly, but you continue 
to ignore them. Initially this could have just been passed off as 
carelessness, but your continuing shows that it can't just be that, but 
must be either stupidity, mental illness, or just that you are a liar.

[toc] | [prev] | [next] | [standalone]


#40768 — Re: I finally completed my lexical analyzer generator ( axiomatic basis )

Fromolcott <NoOne@NoWhere.com>
Date2021-10-24 09:04 -0500
SubjectRe: I finally completed my lexical analyzer generator ( axiomatic basis )
Message-ID<aeydnUhS_8Nn-uj8nZ2dnUU7-UnNnZ2d@giganews.com>
In reply to#40765
On 10/24/2021 5:40 AM, Richard Damon wrote:
> On 10/23/21 11:29 PM, olcott wrote:
>> On 10/23/2021 10:19 PM, Richard Damon wrote:
>>> On 10/23/21 10:16 PM, olcott wrote:
>>>> On 10/23/2021 8:49 PM, Richard Damon wrote:
>>>>>
>>>>> On 10/23/21 9:27 PM, olcott wrote:
>>>>>> In order to make my halt decider a pure function it had to have a 
>>>>>> way to look at the inputs to function calls. In order to look at 
>>>>>> the inputs to function calls it had to know how many inputs that a 
>>>>>> function has.
>>>>>>
>>>>>> This is DFA analyzes C source code to provide the number of 
>>>>>> parameters of each function in the file. The number of parameters 
>>>>>> per function is the number of {vt} matches per {fn} match.
>>>>>>
>>>>>> The only thing that will change with this file is that the halt 
>>>>>> decider will use different halt deciding criteria so that the halt 
>>>>>> decider becomes a pure function.
>>>>>>
>>>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>>>>
>>>>>>
>>>>>> In computer programming, a pure function is a function that has 
>>>>>> the following properties:[1][2]
>>>>>>
>>>>>> (1) The function return values are identical for identical 
>>>>>> arguments (no variation with local static variables, non-local 
>>>>>> variables, mutable reference arguments or input streams).
>>>>>>
>>>>>> (2) The function application has no side effects (no mutation of 
>>>>>> local static variables, non-local variables, mutable reference 
>>>>>> arguments or input/output streams).
>>>>>>
>>>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>>>
>>>>>>
>>>>>>
>>>>>> //
>>>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>>>> //  of C function headers.
>>>>>>
>>>>>> // Character Classes
>>>>>> //
>>>>>>      EMPTY [0]
>>>>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>>>    NUMERIC [0123456789]
>>>>>>         WS [0x09,0x0A,0x0D,0x20]
>>>>>>     LPAREN [(]
>>>>>>     RPAREN [)]
>>>>>>   ASTERISK [*]
>>>>>>      COMMA [,]
>>>>>>    COMMENT [0x2f]
>>>>>>    NEWLINE [0x0A]
>>>>>>      ASCII [0x20-0x7e]
>>>>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>>>
>>>>>>
>>>>>> // Recognized Patterns
>>>>>> //
>>>>>> {et} Empty
>>>>>> {ft} Function_Type
>>>>>> {fn} Function_Name
>>>>>> {vt} Variable_Type
>>>>>> {vn} Variable_Name
>>>>>> {fh} Function_Header
>>>>>>
>>>>>> // DFA Definition to recognize C function headers
>>>>>>
>>>>>> // begin of function type
>>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>>>
>>>>>> // begin of function name
>>>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>>>
>>>>>> // begin of variable type
>>>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>>>>
>>>>>> // begin of variable name
>>>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>>>
>>>>>> // ignores all "//" comments
>>>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>>>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>>>>
>>>>>
>>>>> Ok,
>>>>>
>>>>> Just remember that being a 'Pure Funciton' isn't the actual 
>>>>> requirement, the decider needs to be a Mathematical Computation, 
>>>>> which means that all copies of it, when given the same inputs, 
>>>>> generates the same outputs.
>>>>>
>>>>> You STILL have the error that you treat H as a 'pure simulator' 
>>>>> when it is not, it is only a 'pure simulatior until' and as such, 
>>>>> the behavior of the copy of H in H^ DOES have an affect on the 
>>>>> behavior of that H^. Remember, a 'Pure Simulator' (aka a UTM) NEVER 
>>>>> stops simulating until the machine it is simulating ends, even if 
>>>>> that takes forever.
>>>>>
>>>>
>>>> void Infinite_Loop()
>>>> {
>>>>    HERE: goto HERE;
>>>> }
>>>>
>>>> _Infinite_Loop()
>>>> [00000ab0](01)  55              push ebp
>>>> [00000ab1](02)  8bec            mov ebp,esp
>>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>>> [00000ab5](01)  5d              pop ebp
>>>> [00000ab6](01)  c3              ret
>>>> Size in bytes:(0007) [00000ab6]
>>>>
>>>> Are you saying that the only way that a simulating halt decider can 
>>>> correctly decide that the above code will never stop running is to 
>>>> wait until the end of time?
>>>>
>>>
>>> No. You seem to have a reading comprension problem.
>>>
>>> The Simulating Halt Decider is fully allowed to abort the simulation 
>>> of the machine it is simulationg.
>>>
>>> The only issue is that IF it does so, it can't treat itself as if it 
>>> was a UTM/Pure SImulator, and thus the fact that it never saw the 
>>> comptation reach a halting state isn't proof of anything.
>>
>> When a simulating halt decider acts as if it is a pure simulator and 
>> watches the behavior of an infinite loop it can correctly abort the 
>> simulation of this input and report that this input never halts. We 
>> can generalize this simplest case of infinite execution to all other 
>> cases:
>>
>> All that I am doing is generalizing this same idea. When-so-ever a 
>> simulating halt decider can correctly axiomatically determine that its 
>> input would never halt if it remained a pure simulator then it can 
>> abort the simulation of this input and report that this input never 
>> halts.
>>
>> When a simulating halt decider correctly axiomatically determines X 
>> then we know that X is necessarily true.
>>
>>
> 
> NO!
> 
> You are making an INCORRECT generalization. 

When-so-ever X is correct about Y then X is not incorrect about Y is 
always true.

> t is just like claiming 
> that log(a+b+c) is log(a) + log(b) + log(c) because we have the case 
> that log(1+2+3) = log(1) + log(2) + log(3).
> 
> You have made a claim, PROVE IT. Not just a rhetorical argument done 
> with vague words, but an honest to god actual analytical proof, using 
> the exact same accepted definitions of all the words. And then go and 
> prove that setup does meet the conditions required by the proof to use it.
> 
> You say 'axiomatically', but that is just YOUR DISHONEST DOGDE to insert 
> in a statement that is FALSE.
> 
> Now, part of the problem is that you make a number of small errors that 
> you continue to just ignore and these build up to your false conclusion.
> 
> Your statement would be correct if pronoun usage was correct and the 
> usage refered to just this one COPY being adjusted, and not the shared 
> copy being changed, which causes the change to change the supposed to be 
> fixed algorithm employed by the input being simulated. We know that for 
> THAT case, H is incorrect, as using an ACTUAL 'Pure Simulator' to 
> process this input (where H^ still uses the original H that does abort) 
> shows that H^ WILL HALT, and thus the claim "would not halt unless H 
> aborts the simulation" is incorrect.
> 

_Infinite_Loop()
[00000ab0](01)  55              push ebp
[00000ab1](02)  8bec            mov ebp,esp
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab5](01)  5d              pop ebp
[00000ab6](01)  c3              ret
Size in bytes:(0007) [00000ab6]

It is always the same process. H simulates its input until it determines 
that its input would never halt.

Here is what the above simulation looks like:

[00000ab0](01)  55              push ebp
[00000ab1](02)  8bec            mov ebp,esp
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3
[00000ab3](02)  ebfe            jmp 00000ab3

Can you understand in this simplest possible case that the above is a 
non halting behavior pattern?

> These errors have been pointed out to you repeatedly, but you continue 
> to ignore them. Initially this could have just been passed off as 
> carelessness, but your continuing shows that it can't just be that, but 
> must be either stupidity, mental illness, or just that you are a liar.
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40778 — Re: I finally completed my lexical analyzer generator ( axiomatic basis )

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-24 13:37 -0400
SubjectRe: I finally completed my lexical analyzer generator ( axiomatic basis )
Message-ID<5RgdJ.33089$1n1.21256@fx48.iad>
In reply to#40768
On 10/24/21 10:04 AM, olcott wrote:
> On 10/24/2021 5:40 AM, Richard Damon wrote:
>> On 10/23/21 11:29 PM, olcott wrote:
>>> On 10/23/2021 10:19 PM, Richard Damon wrote:
>>>> On 10/23/21 10:16 PM, olcott wrote:
>>>>> On 10/23/2021 8:49 PM, Richard Damon wrote:
>>>>>>
>>>>>> On 10/23/21 9:27 PM, olcott wrote:
>>>>>>> In order to make my halt decider a pure function it had to have a 
>>>>>>> way to look at the inputs to function calls. In order to look at 
>>>>>>> the inputs to function calls it had to know how many inputs that 
>>>>>>> a function has.
>>>>>>>
>>>>>>> This is DFA analyzes C source code to provide the number of 
>>>>>>> parameters of each function in the file. The number of parameters 
>>>>>>> per function is the number of {vt} matches per {fn} match.
>>>>>>>
>>>>>>> The only thing that will change with this file is that the halt 
>>>>>>> decider will use different halt deciding criteria so that the 
>>>>>>> halt decider becomes a pure function.
>>>>>>>
>>>>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>>>>>
>>>>>>>
>>>>>>> In computer programming, a pure function is a function that has 
>>>>>>> the following properties:[1][2]
>>>>>>>
>>>>>>> (1) The function return values are identical for identical 
>>>>>>> arguments (no variation with local static variables, non-local 
>>>>>>> variables, mutable reference arguments or input streams).
>>>>>>>
>>>>>>> (2) The function application has no side effects (no mutation of 
>>>>>>> local static variables, non-local variables, mutable reference 
>>>>>>> arguments or input/output streams).
>>>>>>>
>>>>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> //
>>>>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>>>>> //  of C function headers.
>>>>>>>
>>>>>>> // Character Classes
>>>>>>> //
>>>>>>>      EMPTY [0]
>>>>>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>>>>    NUMERIC [0123456789]
>>>>>>>         WS [0x09,0x0A,0x0D,0x20]
>>>>>>>     LPAREN [(]
>>>>>>>     RPAREN [)]
>>>>>>>   ASTERISK [*]
>>>>>>>      COMMA [,]
>>>>>>>    COMMENT [0x2f]
>>>>>>>    NEWLINE [0x0A]
>>>>>>>      ASCII [0x20-0x7e]
>>>>>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>>>>
>>>>>>>
>>>>>>> // Recognized Patterns
>>>>>>> //
>>>>>>> {et} Empty
>>>>>>> {ft} Function_Type
>>>>>>> {fn} Function_Name
>>>>>>> {vt} Variable_Type
>>>>>>> {vn} Variable_Name
>>>>>>> {fh} Function_Header
>>>>>>>
>>>>>>> // DFA Definition to recognize C function headers
>>>>>>>
>>>>>>> // begin of function type
>>>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>>>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>>>>
>>>>>>> // begin of function name
>>>>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>>>>
>>>>>>> // begin of variable type
>>>>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>>>>>
>>>>>>> // begin of variable name
>>>>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>>>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>>>>
>>>>>>> // ignores all "//" comments
>>>>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>>>>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>>>>>
>>>>>>
>>>>>> Ok,
>>>>>>
>>>>>> Just remember that being a 'Pure Funciton' isn't the actual 
>>>>>> requirement, the decider needs to be a Mathematical Computation, 
>>>>>> which means that all copies of it, when given the same inputs, 
>>>>>> generates the same outputs.
>>>>>>
>>>>>> You STILL have the error that you treat H as a 'pure simulator' 
>>>>>> when it is not, it is only a 'pure simulatior until' and as such, 
>>>>>> the behavior of the copy of H in H^ DOES have an affect on the 
>>>>>> behavior of that H^. Remember, a 'Pure Simulator' (aka a UTM) 
>>>>>> NEVER stops simulating until the machine it is simulating ends, 
>>>>>> even if that takes forever.
>>>>>>
>>>>>
>>>>> void Infinite_Loop()
>>>>> {
>>>>>    HERE: goto HERE;
>>>>> }
>>>>>
>>>>> _Infinite_Loop()
>>>>> [00000ab0](01)  55              push ebp
>>>>> [00000ab1](02)  8bec            mov ebp,esp
>>>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>>>> [00000ab5](01)  5d              pop ebp
>>>>> [00000ab6](01)  c3              ret
>>>>> Size in bytes:(0007) [00000ab6]
>>>>>
>>>>> Are you saying that the only way that a simulating halt decider can 
>>>>> correctly decide that the above code will never stop running is to 
>>>>> wait until the end of time?
>>>>>
>>>>
>>>> No. You seem to have a reading comprension problem.
>>>>
>>>> The Simulating Halt Decider is fully allowed to abort the simulation 
>>>> of the machine it is simulationg.
>>>>
>>>> The only issue is that IF it does so, it can't treat itself as if it 
>>>> was a UTM/Pure SImulator, and thus the fact that it never saw the 
>>>> comptation reach a halting state isn't proof of anything.
>>>
>>> When a simulating halt decider acts as if it is a pure simulator and 
>>> watches the behavior of an infinite loop it can correctly abort the 
>>> simulation of this input and report that this input never halts. We 
>>> can generalize this simplest case of infinite execution to all other 
>>> cases:
>>>
>>> All that I am doing is generalizing this same idea. When-so-ever a 
>>> simulating halt decider can correctly axiomatically determine that 
>>> its input would never halt if it remained a pure simulator then it 
>>> can abort the simulation of this input and report that this input 
>>> never halts.
>>>
>>> When a simulating halt decider correctly axiomatically determines X 
>>> then we know that X is necessarily true.
>>>
>>>
>>
>> NO!
>>
>> You are making an INCORRECT generalization. 
> 
> When-so-ever X is correct about Y then X is not incorrect about Y is 
> always true.

And if X is not correct about all Y then X is not correct for all Y.

Just because some statement happens to be correct in one case does not 
make it correct in all cases. It might be, but that generalization needs 
to be PROVEN to be used.

FAIL.

Examples NEVER, by themselves prove a generality. An example can prove 
existance, but not that it is true for all cases.

> 
>> t is just like claiming that log(a+b+c) is log(a) + log(b) + log(c) 
>> because we have the case that log(1+2+3) = log(1) + log(2) + log(3).
>>
>> You have made a claim, PROVE IT. Not just a rhetorical argument done 
>> with vague words, but an honest to god actual analytical proof, using 
>> the exact same accepted definitions of all the words. And then go and 
>> prove that setup does meet the conditions required by the proof to use 
>> it.
>>
>> You say 'axiomatically', but that is just YOUR DISHONEST DOGDE to 
>> insert in a statement that is FALSE.
>>
>> Now, part of the problem is that you make a number of small errors 
>> that you continue to just ignore and these build up to your false 
>> conclusion.
>>
>> Your statement would be correct if pronoun usage was correct and the 
>> usage refered to just this one COPY being adjusted, and not the shared 
>> copy being changed, which causes the change to change the supposed to 
>> be fixed algorithm employed by the input being simulated. We know that 
>> for THAT case, H is incorrect, as using an ACTUAL 'Pure Simulator' to 
>> process this input (where H^ still uses the original H that does 
>> abort) shows that H^ WILL HALT, and thus the claim "would not halt 
>> unless H aborts the simulation" is incorrect.
>>
> 
> _Infinite_Loop()
> [00000ab0](01)  55              push ebp
> [00000ab1](02)  8bec            mov ebp,esp
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab5](01)  5d              pop ebp
> [00000ab6](01)  c3              ret
> Size in bytes:(0007) [00000ab6]
> 
> It is always the same process. H simulates its input until it determines 
> that its input would never halt.
> 
> Here is what the above simulation looks like:
> 
> [00000ab0](01)  55              push ebp
> [00000ab1](02)  8bec            mov ebp,esp
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> [00000ab3](02)  ebfe            jmp 00000ab3
> 
> Can you understand in this simplest possible case that the above is a 
> non halting behavior pattern?

You keep using this strawman.

I have never said that a simulating halting decider can't abort a 
simulation or be able to decide on these simple cases.

The problem is that you use a BAD PATTERN to determine that H^ is 
non-halting. You use a pattern based on UNSOUND logic that gives 
incorrect answers for some cases.

GIGO

The fact that you keep going back to showing that it works in some cases 
rather that actually trying to prove that you pattern is correct seems 
to show that you KNOW where your problem is and are trying to cover it up.

The basic concept of having patterns is valid.

The method you use to gather your trace and the pattern you use are not.

It is NOT valid to ignore copies of the decider that are in the machines 
that are being decide.

It is NOT valid to presume that the copies of the decider that are in 
the machines that are being decided are 'unconditional' code.

These are UNPROVEN and in fact INCORRECT presumptions in your pattern

You failure to see this shows that you are just a pathological liar.

> 
>> These errors have been pointed out to you repeatedly, but you continue 
>> to ignore them. Initially this could have just been passed off as 
>> carelessness, but your continuing shows that it can't just be that, 
>> but must be either stupidity, mental illness, or just that you are a 
>> liar.
>>
> 
> 

[toc] | [prev] | [next] | [standalone]


#40790 — Re: I finally completed my lexical analyzer generator ( semantic tautology )

Fromolcott <NoOne@NoWhere.com>
Date2021-10-25 10:02 -0500
SubjectRe: I finally completed my lexical analyzer generator ( semantic tautology )
Message-ID<0YednToPkq-aWuv8nZ2dnUU78LvNnZ2d@giganews.com>
In reply to#40778
On 10/24/2021 12:37 PM, Richard Damon wrote:
> On 10/24/21 10:04 AM, olcott wrote:
>> On 10/24/2021 5:40 AM, Richard Damon wrote:
>>> On 10/23/21 11:29 PM, olcott wrote:
>>>> On 10/23/2021 10:19 PM, Richard Damon wrote:
>>>>> On 10/23/21 10:16 PM, olcott wrote:
>>>>>> On 10/23/2021 8:49 PM, Richard Damon wrote:
>>>>>>>
>>>>>>> On 10/23/21 9:27 PM, olcott wrote:
>>>>>>>> In order to make my halt decider a pure function it had to have 
>>>>>>>> a way to look at the inputs to function calls. In order to look 
>>>>>>>> at the inputs to function calls it had to know how many inputs 
>>>>>>>> that a function has.
>>>>>>>>
>>>>>>>> This is DFA analyzes C source code to provide the number of 
>>>>>>>> parameters of each function in the file. The number of 
>>>>>>>> parameters per function is the number of {vt} matches per {fn} 
>>>>>>>> match.
>>>>>>>>
>>>>>>>> The only thing that will change with this file is that the halt 
>>>>>>>> decider will use different halt deciding criteria so that the 
>>>>>>>> halt decider becomes a pure function.
>>>>>>>>
>>>>>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>>>>>>
>>>>>>>>
>>>>>>>> In computer programming, a pure function is a function that has 
>>>>>>>> the following properties:[1][2]
>>>>>>>>
>>>>>>>> (1) The function return values are identical for identical 
>>>>>>>> arguments (no variation with local static variables, non-local 
>>>>>>>> variables, mutable reference arguments or input streams).
>>>>>>>>
>>>>>>>> (2) The function application has no side effects (no mutation of 
>>>>>>>> local static variables, non-local variables, mutable reference 
>>>>>>>> arguments or input/output streams).
>>>>>>>>
>>>>>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> //
>>>>>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>>>>>> //  of C function headers.
>>>>>>>>
>>>>>>>> // Character Classes
>>>>>>>> //
>>>>>>>>      EMPTY [0]
>>>>>>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>>>>>    NUMERIC [0123456789]
>>>>>>>>         WS [0x09,0x0A,0x0D,0x20]
>>>>>>>>     LPAREN [(]
>>>>>>>>     RPAREN [)]
>>>>>>>>   ASTERISK [*]
>>>>>>>>      COMMA [,]
>>>>>>>>    COMMENT [0x2f]
>>>>>>>>    NEWLINE [0x0A]
>>>>>>>>      ASCII [0x20-0x7e]
>>>>>>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>>>>>
>>>>>>>>
>>>>>>>> // Recognized Patterns
>>>>>>>> //
>>>>>>>> {et} Empty
>>>>>>>> {ft} Function_Type
>>>>>>>> {fn} Function_Name
>>>>>>>> {vt} Variable_Type
>>>>>>>> {vn} Variable_Name
>>>>>>>> {fh} Function_Header
>>>>>>>>
>>>>>>>> // DFA Definition to recognize C function headers
>>>>>>>>
>>>>>>>> // begin of function type
>>>>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>>>>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>>>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>>>>>
>>>>>>>> // begin of function name
>>>>>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>>>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>>>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>>>>>
>>>>>>>> // begin of variable type
>>>>>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>>>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>>>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>>>>>>
>>>>>>>> // begin of variable name
>>>>>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>>>>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>>>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>>>>>
>>>>>>>> // ignores all "//" comments
>>>>>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>>>>>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>>>>>>
>>>>>>>
>>>>>>> Ok,
>>>>>>>
>>>>>>> Just remember that being a 'Pure Funciton' isn't the actual 
>>>>>>> requirement, the decider needs to be a Mathematical Computation, 
>>>>>>> which means that all copies of it, when given the same inputs, 
>>>>>>> generates the same outputs.
>>>>>>>
>>>>>>> You STILL have the error that you treat H as a 'pure simulator' 
>>>>>>> when it is not, it is only a 'pure simulatior until' and as such, 
>>>>>>> the behavior of the copy of H in H^ DOES have an affect on the 
>>>>>>> behavior of that H^. Remember, a 'Pure Simulator' (aka a UTM) 
>>>>>>> NEVER stops simulating until the machine it is simulating ends, 
>>>>>>> even if that takes forever.
>>>>>>>
>>>>>>
>>>>>> void Infinite_Loop()
>>>>>> {
>>>>>>    HERE: goto HERE;
>>>>>> }
>>>>>>
>>>>>> _Infinite_Loop()
>>>>>> [00000ab0](01)  55              push ebp
>>>>>> [00000ab1](02)  8bec            mov ebp,esp
>>>>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>>>>> [00000ab5](01)  5d              pop ebp
>>>>>> [00000ab6](01)  c3              ret
>>>>>> Size in bytes:(0007) [00000ab6]
>>>>>>
>>>>>> Are you saying that the only way that a simulating halt decider 
>>>>>> can correctly decide that the above code will never stop running 
>>>>>> is to wait until the end of time?
>>>>>>
>>>>>
>>>>> No. You seem to have a reading comprension problem.
>>>>>
>>>>> The Simulating Halt Decider is fully allowed to abort the 
>>>>> simulation of the machine it is simulationg.
>>>>>
>>>>> The only issue is that IF it does so, it can't treat itself as if 
>>>>> it was a UTM/Pure SImulator, and thus the fact that it never saw 
>>>>> the comptation reach a halting state isn't proof of anything.
>>>>
>>>> When a simulating halt decider acts as if it is a pure simulator and 
>>>> watches the behavior of an infinite loop it can correctly abort the 
>>>> simulation of this input and report that this input never halts. We 
>>>> can generalize this simplest case of infinite execution to all other 
>>>> cases:
>>>>
>>>> All that I am doing is generalizing this same idea. When-so-ever a 
>>>> simulating halt decider can correctly axiomatically determine that 
>>>> its input would never halt if it remained a pure simulator then it 
>>>> can abort the simulation of this input and report that this input 
>>>> never halts.
>>>>
>>>> When a simulating halt decider correctly axiomatically determines X 
>>>> then we know that X is necessarily true.
>>>>
>>>>
>>>
>>> NO!
>>>
>>> You are making an INCORRECT generalization. 
>>
>> When-so-ever X is correct about Y then X is not incorrect about Y is 
>> always true.
> 
> And if X is not correct about all Y then X is not correct for all Y.

Y is a specific unique instance.

> Just because some statement happens to be correct in one case does not 
> make it correct in all cases. 

Just because some statement is correct in one case conclusively proves 
that this statement is not incorrect in all cases.

> It might be, but that generalization needs 
> to be PROVEN to be used.
> 
> FAIL.
> 
> Examples NEVER, by themselves prove a generality.

One single counter-example does correctly refute a general statement.
Linz claims that no H can correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩ 
thus a single H that does correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩ 
refutes Linz.

>  An example can prove 
> existance, but not that it is true for all cases.
> 
>>
>>> t is just like claiming that log(a+b+c) is log(a) + log(b) + log(c) 
>>> because we have the case that log(1+2+3) = log(1) + log(2) + log(3).
>>>
>>> You have made a claim, PROVE IT. Not just a rhetorical argument done 
>>> with vague words, but an honest to god actual analytical proof, using 
>>> the exact same accepted definitions of all the words. And then go and 
>>> prove that setup does meet the conditions required by the proof to 
>>> use it.
>>>
>>> You say 'axiomatically', but that is just YOUR DISHONEST DOGDE to 
>>> insert in a statement that is FALSE.
>>>
>>> Now, part of the problem is that you make a number of small errors 
>>> that you continue to just ignore and these build up to your false 
>>> conclusion.
>>>
>>> Your statement would be correct if pronoun usage was correct and the 
>>> usage refered to just this one COPY being adjusted, and not the 
>>> shared copy being changed, which causes the change to change the 
>>> supposed to be fixed algorithm employed by the input being simulated. 
>>> We know that for THAT case, H is incorrect, as using an ACTUAL 'Pure 
>>> Simulator' to process this input (where H^ still uses the original H 
>>> that does abort) shows that H^ WILL HALT, and thus the claim "would 
>>> not halt unless H aborts the simulation" is incorrect.
>>>
>>
>> _Infinite_Loop()
>> [00000ab0](01)  55              push ebp
>> [00000ab1](02)  8bec            mov ebp,esp
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab5](01)  5d              pop ebp
>> [00000ab6](01)  c3              ret
>> Size in bytes:(0007) [00000ab6]
>>
>> It is always the same process. H simulates its input until it 
>> determines that its input would never halt.
>>
>> Here is what the above simulation looks like:
>>
>> [00000ab0](01)  55              push ebp
>> [00000ab1](02)  8bec            mov ebp,esp
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>> [00000ab3](02)  ebfe            jmp 00000ab3
>>
>> Can you understand in this simplest possible case that the above is a 
>> non halting behavior pattern?
> 
> You keep using this strawman.
> 
> I have never said that a simulating halting decider can't abort a 
> simulation or be able to decide on these simple cases.
> 

Then we can proceed step-by-step increasing the difficulty by minimal 
increments until we get to H(P,P). The correct halt status of H(P,P) is 
based on the correct halt status of infinite recursion.

> The problem is that you use a BAD PATTERN to determine that H^ is 
> non-halting. You use a pattern based on UNSOUND logic that gives 
> incorrect answers for some cases.
> 

If it is true that the infinite simulation of the input to H(P,P) never 
reaches its final state then when H stops simulating this input and 
reports that this input never halts we know that H has correctly decided 
the halt status of its input by semantic tautology.

Even when H aborts the simulation of this input this does not count as 
halting because P never reaches its final state.

A simpler version of this same semantic tautology:
If H correctly decides that its input never halts then H is not incorrect.

The simplest version of this same semantic tautology:
If H is correct then H is not incorrect.




-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40806 — Re: I finally completed my lexical analyzer generator ( semantic tautology )

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-25 19:40 -0400
SubjectRe: I finally completed my lexical analyzer generator ( semantic tautology )
Message-ID<CfHdJ.120$QB1.113@fx42.iad>
In reply to#40790
On 10/25/21 11:02 AM, olcott wrote:
> On 10/24/2021 12:37 PM, Richard Damon wrote:
>> On 10/24/21 10:04 AM, olcott wrote:
>>> On 10/24/2021 5:40 AM, Richard Damon wrote:
>>>> On 10/23/21 11:29 PM, olcott wrote:
>>>>> On 10/23/2021 10:19 PM, Richard Damon wrote:
>>>>>> On 10/23/21 10:16 PM, olcott wrote:
>>>>>>> On 10/23/2021 8:49 PM, Richard Damon wrote:
>>>>>>>>
>>>>>>>> On 10/23/21 9:27 PM, olcott wrote:
>>>>>>>>> In order to make my halt decider a pure function it had to have 
>>>>>>>>> a way to look at the inputs to function calls. In order to look 
>>>>>>>>> at the inputs to function calls it had to know how many inputs 
>>>>>>>>> that a function has.
>>>>>>>>>
>>>>>>>>> This is DFA analyzes C source code to provide the number of 
>>>>>>>>> parameters of each function in the file. The number of 
>>>>>>>>> parameters per function is the number of {vt} matches per {fn} 
>>>>>>>>> match.
>>>>>>>>>
>>>>>>>>> The only thing that will change with this file is that the halt 
>>>>>>>>> decider will use different halt deciding criteria so that the 
>>>>>>>>> halt decider becomes a pure function.
>>>>>>>>>
>>>>>>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> In computer programming, a pure function is a function that has 
>>>>>>>>> the following properties:[1][2]
>>>>>>>>>
>>>>>>>>> (1) The function return values are identical for identical 
>>>>>>>>> arguments (no variation with local static variables, non-local 
>>>>>>>>> variables, mutable reference arguments or input streams).
>>>>>>>>>
>>>>>>>>> (2) The function application has no side effects (no mutation 
>>>>>>>>> of local static variables, non-local variables, mutable 
>>>>>>>>> reference arguments or input/output streams).
>>>>>>>>>
>>>>>>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> //
>>>>>>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>>>>>>> //  of C function headers.
>>>>>>>>>
>>>>>>>>> // Character Classes
>>>>>>>>> //
>>>>>>>>>      EMPTY [0]
>>>>>>>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>>>>>>    NUMERIC [0123456789]
>>>>>>>>>         WS [0x09,0x0A,0x0D,0x20]
>>>>>>>>>     LPAREN [(]
>>>>>>>>>     RPAREN [)]
>>>>>>>>>   ASTERISK [*]
>>>>>>>>>      COMMA [,]
>>>>>>>>>    COMMENT [0x2f]
>>>>>>>>>    NEWLINE [0x0A]
>>>>>>>>>      ASCII [0x20-0x7e]
>>>>>>>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> // Recognized Patterns
>>>>>>>>> //
>>>>>>>>> {et} Empty
>>>>>>>>> {ft} Function_Type
>>>>>>>>> {fn} Function_Name
>>>>>>>>> {vt} Variable_Type
>>>>>>>>> {vn} Variable_Name
>>>>>>>>> {fh} Function_Header
>>>>>>>>>
>>>>>>>>> // DFA Definition to recognize C function headers
>>>>>>>>>
>>>>>>>>> // begin of function type
>>>>>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>>>>>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>>>>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>>>>>>
>>>>>>>>> // begin of function name
>>>>>>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>>>>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>>>>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>>>>>>
>>>>>>>>> // begin of variable type
>>>>>>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>>>>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>>>>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>>>>>>>
>>>>>>>>> // begin of variable name
>>>>>>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>>>>>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>>>>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>>>>>>
>>>>>>>>> // ignores all "//" comments
>>>>>>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>>>>>>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>>>>>>>
>>>>>>>>
>>>>>>>> Ok,
>>>>>>>>
>>>>>>>> Just remember that being a 'Pure Funciton' isn't the actual 
>>>>>>>> requirement, the decider needs to be a Mathematical Computation, 
>>>>>>>> which means that all copies of it, when given the same inputs, 
>>>>>>>> generates the same outputs.
>>>>>>>>
>>>>>>>> You STILL have the error that you treat H as a 'pure simulator' 
>>>>>>>> when it is not, it is only a 'pure simulatior until' and as 
>>>>>>>> such, the behavior of the copy of H in H^ DOES have an affect on 
>>>>>>>> the behavior of that H^. Remember, a 'Pure Simulator' (aka a 
>>>>>>>> UTM) NEVER stops simulating until the machine it is simulating 
>>>>>>>> ends, even if that takes forever.
>>>>>>>>
>>>>>>>
>>>>>>> void Infinite_Loop()
>>>>>>> {
>>>>>>>    HERE: goto HERE;
>>>>>>> }
>>>>>>>
>>>>>>> _Infinite_Loop()
>>>>>>> [00000ab0](01)  55              push ebp
>>>>>>> [00000ab1](02)  8bec            mov ebp,esp
>>>>>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>>>>>> [00000ab5](01)  5d              pop ebp
>>>>>>> [00000ab6](01)  c3              ret
>>>>>>> Size in bytes:(0007) [00000ab6]
>>>>>>>
>>>>>>> Are you saying that the only way that a simulating halt decider 
>>>>>>> can correctly decide that the above code will never stop running 
>>>>>>> is to wait until the end of time?
>>>>>>>
>>>>>>
>>>>>> No. You seem to have a reading comprension problem.
>>>>>>
>>>>>> The Simulating Halt Decider is fully allowed to abort the 
>>>>>> simulation of the machine it is simulationg.
>>>>>>
>>>>>> The only issue is that IF it does so, it can't treat itself as if 
>>>>>> it was a UTM/Pure SImulator, and thus the fact that it never saw 
>>>>>> the comptation reach a halting state isn't proof of anything.
>>>>>
>>>>> When a simulating halt decider acts as if it is a pure simulator 
>>>>> and watches the behavior of an infinite loop it can correctly abort 
>>>>> the simulation of this input and report that this input never 
>>>>> halts. We can generalize this simplest case of infinite execution 
>>>>> to all other cases:
>>>>>
>>>>> All that I am doing is generalizing this same idea. When-so-ever a 
>>>>> simulating halt decider can correctly axiomatically determine that 
>>>>> its input would never halt if it remained a pure simulator then it 
>>>>> can abort the simulation of this input and report that this input 
>>>>> never halts.
>>>>>
>>>>> When a simulating halt decider correctly axiomatically determines X 
>>>>> then we know that X is necessarily true.
>>>>>
>>>>>
>>>>
>>>> NO!
>>>>
>>>> You are making an INCORRECT generalization. 
>>>
>>> When-so-ever X is correct about Y then X is not incorrect about Y is 
>>> always true.
>>
>> And if X is not correct about all Y then X is not correct for all Y.
> 
> Y is a specific unique instance.

But not the right one.

You have shown your method works for Infinite_Loop and 
Infinite_Recursion but not for H^ (which is NOT non-halting if H give 
the non-halting answer).

> 
>> Just because some statement happens to be correct in one case does not 
>> make it correct in all cases. 
> 
> Just because some statement is correct in one case conclusively proves 
> that this statement is not incorrect in all cases.

No one said it was incorrect in all cases. H might be right for many 
machines, just not for H^.

> 
>> It might be, but that generalization needs to be PROVEN to be used.
>>
>> FAIL.
>>
>> Examples NEVER, by themselves prove a generality.
> 
> One single counter-example does correctly refute a general statement.
> Linz claims that no H can correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩ 
> thus a single H that does correctly decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩ 
> refutes Linz.
> 

But you DON'T get H(<H^>,<H^>) right. Your H says that the computation 
H^(<H^>) is non-halting, but it actually is Halting.

Your arguments just show that H can never see that halting state because 
H will always abort its simulation too soon because is uses unsound 
readoning.

>>  An example can prove existance, but not that it is true for all cases.
>>
>>>
>>>> t is just like claiming that log(a+b+c) is log(a) + log(b) + log(c) 
>>>> because we have the case that log(1+2+3) = log(1) + log(2) + log(3).
>>>>
>>>> You have made a claim, PROVE IT. Not just a rhetorical argument done 
>>>> with vague words, but an honest to god actual analytical proof, 
>>>> using the exact same accepted definitions of all the words. And then 
>>>> go and prove that setup does meet the conditions required by the 
>>>> proof to use it.
>>>>
>>>> You say 'axiomatically', but that is just YOUR DISHONEST DOGDE to 
>>>> insert in a statement that is FALSE.
>>>>
>>>> Now, part of the problem is that you make a number of small errors 
>>>> that you continue to just ignore and these build up to your false 
>>>> conclusion.
>>>>
>>>> Your statement would be correct if pronoun usage was correct and the 
>>>> usage refered to just this one COPY being adjusted, and not the 
>>>> shared copy being changed, which causes the change to change the 
>>>> supposed to be fixed algorithm employed by the input being 
>>>> simulated. We know that for THAT case, H is incorrect, as using an 
>>>> ACTUAL 'Pure Simulator' to process this input (where H^ still uses 
>>>> the original H that does abort) shows that H^ WILL HALT, and thus 
>>>> the claim "would not halt unless H aborts the simulation" is incorrect.
>>>>
>>>
>>> _Infinite_Loop()
>>> [00000ab0](01)  55              push ebp
>>> [00000ab1](02)  8bec            mov ebp,esp
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab5](01)  5d              pop ebp
>>> [00000ab6](01)  c3              ret
>>> Size in bytes:(0007) [00000ab6]
>>>
>>> It is always the same process. H simulates its input until it 
>>> determines that its input would never halt.
>>>
>>> Here is what the above simulation looks like:
>>>
>>> [00000ab0](01)  55              push ebp
>>> [00000ab1](02)  8bec            mov ebp,esp
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>> [00000ab3](02)  ebfe            jmp 00000ab3
>>>
>>> Can you understand in this simplest possible case that the above is a 
>>> non halting behavior pattern?
>>
>> You keep using this strawman.
>>
>> I have never said that a simulating halting decider can't abort a 
>> simulation or be able to decide on these simple cases.
>>
> 
> Then we can proceed step-by-step increasing the difficulty by minimal 
> increments until we get to H(P,P). The correct halt status of H(P,P) is 
> based on the correct halt status of infinite recursion.

But it DOESN'T have infinite recursion, at least not for any H that 
reports that H*(P,P) is non-halting, as that H will abort the recursion 
at some finite point.

Remember, for a given P, the H is fixed, and either H fails to answer or 
P(P) will halt. You get this messed up and look at a P built by a 
different H.

Yes, for Hn that doesn't abort, Pn is non-haling, but Hn doesn't sayd 
that it is because it also is non-halting.

for Ha that does does abort, Pa is Halting, but Ha says it is non-haling.

Yes Ha can correctly decide that Pn is non-halting and Hn can corrrectly 
decide that Pa is Halting, but those are not the required matchups. Hx 
needs to decide on Px, not some other version of P.

> 
>> The problem is that you use a BAD PATTERN to determine that H^ is 
>> non-halting. You use a pattern based on UNSOUND logic that gives 
>> incorrect answers for some cases.
>>
> 
> If it is true that the infinite simulation of the input to H(P,P) never 
> reaches its final state then when H stops simulating this input and 
> reports that this input never halts we know that H has correctly decided 
> the halt status of its input by semantic tautology.
> 

U(P,P) is Halting, at least if H does abort is simulation of P(P) and 
answers non-halting. So you are incorrect there.

Yes, if H is Hn that doesn't abort its simulation, then the Pn built on 
it doesn't halt, but also Hn(Pn,Pn) doesn't answer so it is still wrong.

> Even when H aborts the simulation of this input this does not count as 
> halting because P never reaches its final state.

The fact that the PARTIAL simulation of P(P) doesn't reach the halting 
state proves NOTHING. You foget the fact that H is answering about the 
ACTUAL Computation P(P), not its own partial simulation, and the actual 
computaiton does finish at a halting state.

> 
> A simpler version of this same semantic tautology:
> If H correctly decides that its input never halts then H is not incorrect.

Bad Semantics, Inputs don't halt.

The ACTUAL criteria that H is SUPPOSED to be answering is "Does the 
Computation REPRESENTED by the input to H halt or not?"

The Computation Represented by the input <P>,<P> is P(<P>) which halts.

> 
> The simplest version of this same semantic tautology:
> If H is correct then H is not incorrect.
> 

No, H is incorrect. FAIL


Your H is only correct about POOP, but no one else cares about that.

[toc] | [prev] | [next] | [standalone]


#40766

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-24 07:59 -0400
Message-ID<FUbdJ.9079$D64.9078@fx41.iad>
In reply to#40760
On 10/23/21 9:27 PM, olcott wrote:
> In order to make my halt decider a pure function it had to have a way to 
> look at the inputs to function calls. In order to look at the inputs to 
> function calls it had to know how many inputs that a function has.
> 
> This is DFA analyzes C source code to provide the number of parameters 
> of each function in the file. The number of parameters per function is 
> the number of {vt} matches per {fn} match.
> 
> The only thing that will change with this file is that the halt decider 
> will use different halt deciding criteria so that the halt decider 
> becomes a pure function.
> 
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
> 
> 
> In computer programming, a pure function is a function that has the 
> following properties:[1][2]
> 
> (1) The function return values are identical for identical arguments (no 
> variation with local static variables, non-local variables, mutable 
> reference arguments or input streams).
> 
> (2) The function application has no side effects (no mutation of local 
> static variables, non-local variables, mutable reference arguments or 
> input/output streams).
> 
> https://en.wikipedia.org/wiki/Pure_function
> 
> 
> 
> //
> //  Deterministic Finite Automaton (DFA) recognizer
> //  of C function headers.
> 
> // Character Classes
> //
>      EMPTY [0]
>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>    NUMERIC [0123456789]
>         WS [0x09,0x0A,0x0D,0x20]
>     LPAREN [(]
>     RPAREN [)]
>   ASTERISK [*]
>      COMMA [,]
>    COMMENT [0x2f]
>    NEWLINE [0x0A]
>      ASCII [0x20-0x7e]
>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
> 
> 
> // Recognized Patterns
> //
> {et} Empty
> {ft} Function_Type
> {fn} Function_Name
> {vt} Variable_Type
> {vn} Variable_Name
> {fh} Function_Header
> 
> // DFA Definition to recognize C function headers
> 
> // begin of function type
> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
> 
> // begin of function name
> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
> 
> // begin of variable type
> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
> 
> // begin of variable name
> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
> 
> // ignores all "//" comments
> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
> 

One thing that I just thought of, this routine that you are using is 
going to need the SOURCE code of the machine. Is your decieer now going 
to take the full source code of the machine as the input instead of the 
compiled object file? Does that mean your decider now includes a full 
compiler as part of it?

[toc] | [prev] | [next] | [standalone]


#40769

Fromolcott <NoOne@NoWhere.com>
Date2021-10-24 09:07 -0500
Message-ID<aeydnUtS_8M99ej8nZ2dnUU7-UmdnZ2d@giganews.com>
In reply to#40766
On 10/24/2021 6:59 AM, Richard Damon wrote:
> On 10/23/21 9:27 PM, olcott wrote:
>> In order to make my halt decider a pure function it had to have a way 
>> to look at the inputs to function calls. In order to look at the 
>> inputs to function calls it had to know how many inputs that a 
>> function has.
>>
>> This is DFA analyzes C source code to provide the number of parameters 
>> of each function in the file. The number of parameters per function is 
>> the number of {vt} matches per {fn} match.
>>
>> The only thing that will change with this file is that the halt 
>> decider will use different halt deciding criteria so that the halt 
>> decider becomes a pure function.
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>
>>
>> In computer programming, a pure function is a function that has the 
>> following properties:[1][2]
>>
>> (1) The function return values are identical for identical arguments 
>> (no variation with local static variables, non-local variables, 
>> mutable reference arguments or input streams).
>>
>> (2) The function application has no side effects (no mutation of local 
>> static variables, non-local variables, mutable reference arguments or 
>> input/output streams).
>>
>> https://en.wikipedia.org/wiki/Pure_function
>>
>>
>>
>> //
>> //  Deterministic Finite Automaton (DFA) recognizer
>> //  of C function headers.
>>
>> // Character Classes
>> //
>>      EMPTY [0]
>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>    NUMERIC [0123456789]
>>         WS [0x09,0x0A,0x0D,0x20]
>>     LPAREN [(]
>>     RPAREN [)]
>>   ASTERISK [*]
>>      COMMA [,]
>>    COMMENT [0x2f]
>>    NEWLINE [0x0A]
>>      ASCII [0x20-0x7e]
>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>
>>
>> // Recognized Patterns
>> //
>> {et} Empty
>> {ft} Function_Type
>> {fn} Function_Name
>> {vt} Variable_Type
>> {vn} Variable_Name
>> {fh} Function_Header
>>
>> // DFA Definition to recognize C function headers
>>
>> // begin of function type
>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>
>> // begin of function name
>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>
>> // begin of variable type
>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>
>> // begin of variable name
>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>
>> // ignores all "//" comments
>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>
> 
> One thing that I just thought of, this routine that you are using is 
> going to need the SOURCE code of the machine. Is your decieer now going 
> to take the full source code of the machine as the input instead of the 
> compiled object file? Does that mean your decider now includes a full 
> compiler as part of it?

The halt decider is merely provided with a function that tells it the 
number of parameters that each function takes.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40779

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-24 13:41 -0400
Message-ID<7VgdJ.33091$1n1.22675@fx48.iad>
In reply to#40769
On 10/24/21 10:07 AM, olcott wrote:
> On 10/24/2021 6:59 AM, Richard Damon wrote:
>> On 10/23/21 9:27 PM, olcott wrote:
>>> In order to make my halt decider a pure function it had to have a way 
>>> to look at the inputs to function calls. In order to look at the 
>>> inputs to function calls it had to know how many inputs that a 
>>> function has.
>>>
>>> This is DFA analyzes C source code to provide the number of 
>>> parameters of each function in the file. The number of parameters per 
>>> function is the number of {vt} matches per {fn} match.
>>>
>>> The only thing that will change with this file is that the halt 
>>> decider will use different halt deciding criteria so that the halt 
>>> decider becomes a pure function.
>>>
>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>>
>>>
>>> In computer programming, a pure function is a function that has the 
>>> following properties:[1][2]
>>>
>>> (1) The function return values are identical for identical arguments 
>>> (no variation with local static variables, non-local variables, 
>>> mutable reference arguments or input streams).
>>>
>>> (2) The function application has no side effects (no mutation of 
>>> local static variables, non-local variables, mutable reference 
>>> arguments or input/output streams).
>>>
>>> https://en.wikipedia.org/wiki/Pure_function
>>>
>>>
>>>
>>> //
>>> //  Deterministic Finite Automaton (DFA) recognizer
>>> //  of C function headers.
>>>
>>> // Character Classes
>>> //
>>>      EMPTY [0]
>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>    NUMERIC [0123456789]
>>>         WS [0x09,0x0A,0x0D,0x20]
>>>     LPAREN [(]
>>>     RPAREN [)]
>>>   ASTERISK [*]
>>>      COMMA [,]
>>>    COMMENT [0x2f]
>>>    NEWLINE [0x0A]
>>>      ASCII [0x20-0x7e]
>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>
>>>
>>> // Recognized Patterns
>>> //
>>> {et} Empty
>>> {ft} Function_Type
>>> {fn} Function_Name
>>> {vt} Variable_Type
>>> {vn} Variable_Name
>>> {fh} Function_Header
>>>
>>> // DFA Definition to recognize C function headers
>>>
>>> // begin of function type
>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12)
>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>
>>> // begin of function name
>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>
>>> // begin of variable type
>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>>>
>>> // begin of variable name
>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00)
>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>
>>> // ignores all "//" comments
>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](00) [/](13)
>>> <13> CONTROL(13) ASCII(13)  [0x0A] (00)
>>>
>>
>> One thing that I just thought of, this routine that you are using is 
>> going to need the SOURCE code of the machine. Is your decieer now 
>> going to take the full source code of the machine as the input instead 
>> of the compiled object file? Does that mean your decider now includes 
>> a full compiler as part of it?
> 
> The halt decider is merely provided with a function that tells it the 
> number of parameters that each function takes.
> 

And if the input to the decider is an executable file, where does it get 
this source code to send to the function?

Or, does your halt decider now have some other input besides the 
encoding of the machine and its input to decide on, and thus isn't 
anything like the halt decider of the Halting Problem?

[toc] | [prev] | [next] | [standalone]


#40780 — Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

Fromolcott <NoOne@NoWhere.com>
Date2021-10-24 13:37 -0500
SubjectRe: I finally completed my lexical analyzer generator (needed by my halt decider) update
Message-ID<GLWdnSs1lLhuOuj8nZ2dnUU7-UnNnZ2d@giganews.com>
In reply to#40760
On 10/23/2021 8:27 PM, olcott wrote:
> In order to make my halt decider a pure function it had to have a way to 
> look at the inputs to function calls. In order to look at the inputs to 
> function calls it had to know how many inputs that a function has.
> 
> This is DFA analyzes C source code to provide the number of parameters 
> of each function in the file. The number of parameters per function is 
> the number of {vt} matches per {fn} match.
> 
> The only thing that will change with this file is that the halt decider 
> will use different halt deciding criteria so that the halt decider 
> becomes a pure function.
> 
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
> 
> 
> In computer programming, a pure function is a function that has the 
> following properties:[1][2]
> 
> (1) The function return values are identical for identical arguments (no 
> variation with local static variables, non-local variables, mutable 
> reference arguments or input streams).
> 
> (2) The function application has no side effects (no mutation of local 
> static variables, non-local variables, mutable reference arguments or 
> input/output streams).
> 
> https://en.wikipedia.org/wiki/Pure_function
> 
> 
Enhancements: (Assumes that the C source code compiles)
(a) Ignores /* */ comments
(b) Ignores #define lines
(c) Correctly handles trailing space in: int Function_Name(void   )

//
//  Deterministic Finite Automaton (DFA) recognizer
//  of C function headers.

// Character Classes
//
     EMPTY [0]
     ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
   NUMERIC [0123456789]
        WS [0x09,0x0A,0x0D,0x20]
    LPAREN [(]
    RPAREN [)]
     POUND [#]
  ASTERISK [*]     // 0x2a
     COMMA [,]

     SLASH [0x2f]  // "/"
   NEWLINE [0x0A]
     ASCII [0x20-0x7e]
      ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
     ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
        ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
   CONTROL [0x00-0x09,0x0b-0x1f,0x7f]

// Recognized Patterns
//
{et} Empty
{ft} Function_Type
{fn} Function_Name
{vt} Variable_Type
{vn} Variable_Name
{fh} Function_Header

// DFA Definition to recognize C function headers

// begin of function type
<00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)
<01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
<02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)

// begin of function name
<03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
<04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
<05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)

// begin of variable type
<06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
<07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
<08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)

// begin of variable name
<09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
<10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
<11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)

// ignores all "//" comments
<12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
<13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)

// look for comment terminator "*/"
<14> ASCII_MINUS_ASTERISK(14) [*](15)
<15>    ASCII_MINUS_SLASH(14) [/](00)



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40781 — Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

FromRichard Damon <Richard@Damon-Family.org>
Date2021-10-24 15:55 -0400
SubjectRe: I finally completed my lexical analyzer generator (needed by my halt decider) update
Message-ID<bTidJ.9898$D64.1912@fx41.iad>
In reply to#40780
On 10/24/21 2:37 PM, olcott wrote:
> On 10/23/2021 8:27 PM, olcott wrote:
>> In order to make my halt decider a pure function it had to have a way 
>> to look at the inputs to function calls. In order to look at the 
>> inputs to function calls it had to know how many inputs that a 
>> function has.
>>
>> This is DFA analyzes C source code to provide the number of parameters 
>> of each function in the file. The number of parameters per function is 
>> the number of {vt} matches per {fn} match.
>>
>> The only thing that will change with this file is that the halt 
>> decider will use different halt deciding criteria so that the halt 
>> decider becomes a pure function.
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
>>
>>
>> In computer programming, a pure function is a function that has the 
>> following properties:[1][2]
>>
>> (1) The function return values are identical for identical arguments 
>> (no variation with local static variables, non-local variables, 
>> mutable reference arguments or input streams).
>>
>> (2) The function application has no side effects (no mutation of local 
>> static variables, non-local variables, mutable reference arguments or 
>> input/output streams).
>>
>> https://en.wikipedia.org/wiki/Pure_function
>>
>>
> Enhancements: (Assumes that the C source code compiles)
> (a) Ignores /* */ comments
> (b) Ignores #define lines
> (c) Correctly handles trailing space in: int Function_Name(void   )
> 
> //
> //  Deterministic Finite Automaton (DFA) recognizer
> //  of C function headers.
> 
> // Character Classes
> //
>      EMPTY [0]
>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>    NUMERIC [0123456789]
>         WS [0x09,0x0A,0x0D,0x20]
>     LPAREN [(]
>     RPAREN [)]
>      POUND [#]
>   ASTERISK [*]     // 0x2a
>      COMMA [,]
> 
>      SLASH [0x2f]  // "/"
>    NEWLINE [0x0A]
>      ASCII [0x20-0x7e]
>       ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
>      ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
>         ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
> 
> // Recognized Patterns
> //
> {et} Empty
> {ft} Function_Type
> {fn} Function_Name
> {vt} Variable_Type
> {vn} Variable_Name
> {fh} Function_Header
> 
> // DFA Definition to recognize C function headers
> 
> // begin of function type
> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)
> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
> 
> // begin of function name
> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
> 
> // begin of variable type
> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
> 
> // begin of variable name
> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
> 
> // ignores all "//" comments
> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
> <13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)
> 
> // look for comment terminator "*/"
> <14> ASCII_MINUS_ASTERISK(14) [*](15)
> <15>    ASCII_MINUS_SLASH(14) [/](00)
> 
> 
> 

And again my question, what good is this if the halt decider is getting 
the compiled version of the code as its input?

If H doesn't have the source code, it can't give what it doesn't have to 
the DFA to get the data it wants.

Or, does the Halt Decider now get the source code and is compiling it 
before running it?

[toc] | [prev] | [next] | [standalone]


#40785 — Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-10-25 02:08 +0100
SubjectRe: I finally completed my lexical analyzer generator (needed by my halt decider) update
Message-ID<87bl3d3o80.fsf@bsb.me.uk>
In reply to#40780
olcott <NoOne@NoWhere.com> writes:

> Enhancements: (Assumes that the C source code compiles)
> (a) Ignores /* */ comments
> (b) Ignores #define lines
> (c) Correctly handles trailing space in: int Function_Name(void   )
>
> //
> //  Deterministic Finite Automaton (DFA) recognizer
> //  of C function headers.
>
> // Character Classes
> //
>     EMPTY [0]
>     ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>   NUMERIC [0123456789]
>        WS [0x09,0x0A,0x0D,0x20]
>    LPAREN [(]
>    RPAREN [)]
>     POUND [#]
>  ASTERISK [*]     // 0x2a
>     COMMA [,]
>     SLASH [0x2f]  // "/"
>   NEWLINE [0x0A]

Why don't you use these last seven?

>     ASCII [0x20-0x7e]
>      ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
>     ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
>        ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
>   CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>
> // Recognized Patterns
> //
> {et} Empty
> {ft} Function_Type
> {fn} Function_Name
> {vt} Variable_Type
> {vn} Variable_Name
> {fh} Function_Header
>
> // DFA Definition to recognize C function headers

No DFA can do that in general.  You mean "recognise a very restricted
subset of C function headers".

> // begin of function type
> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)

What does that [*] mean?  Judging by the other uses of []s, you seem to
be accepting *s and digits at the start of a C function header even
though they won't be taken to be one of your named matches.  Why single
out *s and digits?

> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>
> // begin of function name
> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>
> // begin of variable type
> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)

And all these uses of [*] are very odd.  It seems that after seeing this
string:

  *1*x x(*x x()

your DFA returns to state 0 having seen an {fh}.  Is that right?  Maybe
I've misunderstood the notation.

> // begin of variable name
> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>
> // ignores all "//" comments
> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
> <13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)
>
> // look for comment terminator "*/"
> <14> ASCII_MINUS_ASTERISK(14) [*](15)
> <15>    ASCII_MINUS_SLASH(14) [/](00)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#40786 — Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

Fromolcott <NoOne@NoWhere.com>
Date2021-10-24 20:45 -0500
SubjectRe: I finally completed my lexical analyzer generator (needed by my halt decider) update
Message-ID<xYSdnUeGwL7Okev8nZ2dnUU7-dPNnZ2d@giganews.com>
In reply to#40785
On 10/24/2021 8:08 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> Enhancements: (Assumes that the C source code compiles)
>> (a) Ignores /* */ comments
>> (b) Ignores #define lines
>> (c) Correctly handles trailing space in: int Function_Name(void   )
>>
>> //
>> //  Deterministic Finite Automaton (DFA) recognizer
>> //  of C function headers.
>>
>> // Character Classes
>> //
>>      EMPTY [0]
>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>    NUMERIC [0123456789]
>>         WS [0x09,0x0A,0x0D,0x20]
>>     LPAREN [(]
>>     RPAREN [)]
>>      POUND [#]
>>   ASTERISK [*]     // 0x2a
>>      COMMA [,]
>>      SLASH [0x2f]  // "/"
>>    NEWLINE [0x0A]
> 
> Why don't you use these last seven?
> 

I do use them.
I can refer to either the name or the definition of the character class.
ASCII and CONTROL may be used in the future.

>>      ASCII [0x20-0x7e]
>>       ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
>>      ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
>>         ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>
>> // Recognized Patterns
>> //
>> {et} Empty
>> {ft} Function_Type
>> {fn} Function_Name
>> {vt} Variable_Type
>> {vn} Variable_Name
>> {fh} Function_Header
>>
>> // DFA Definition to recognize C function headers
> 
> No DFA can do that in general.  You mean "recognise a very restricted
> subset of C function headers".
> 

It recognizes everything that I will ever write.

>> // begin of function type
>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)
> 
> What does that [*] mean?  Judging by the other uses of []s, you seem to
> be accepting *s and digits at the start of a C function header even
> though they won't be taken to be one of your named matches.  Why single
> out *s and digits?
> 

int* M(int* N);

>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>
>> // begin of function name
>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>
>> // begin of variable type
>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
> 
> And all these uses of [*] are very odd.  It seems that after seeing this
> string:
> 
>    *1*x x(*x x()
> 

The DFA asumes that its input compiles as C, thus will never see that 
string.

> your DFA returns to state 0 having seen an {fh}.  Is that right?  Maybe
> I've misunderstood the notation.
> 

Yes. In the code that executes the DFA there are semantic actions.
This is the most important semantic action:

bool RecognizedFunctionHeader(u8 OneByte, int State)
{
   return (OneByte == ')' &&
          (State == 6 || State == 7 ||
           State == 9 || State == 10 || State == 11));
}

>> // begin of variable name
>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>
>> // ignores all "//" comments
>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
>> <13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)
>>
>> // look for comment terminator "*/"
>> <14> ASCII_MINUS_ASTERISK(14) [*](15)
>> <15>    ASCII_MINUS_SLASH(14) [/](00)
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40804 — Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-10-26 00:26 +0100
SubjectRe: I finally completed my lexical analyzer generator (needed by my halt decider) update
Message-ID<87wnm01y9s.fsf@bsb.me.uk>
In reply to#40786
olcott <NoOne@NoWhere.com> writes:

> On 10/24/2021 8:08 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> Enhancements: (Assumes that the C source code compiles)
>>> (a) Ignores /* */ comments
>>> (b) Ignores #define lines
>>> (c) Correctly handles trailing space in: int Function_Name(void   )
>>>
>>> //
>>> //  Deterministic Finite Automaton (DFA) recognizer
>>> //  of C function headers.
>>>
>>> // Character Classes
>>> //
>>>      EMPTY [0]
>>>      ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>    NUMERIC [0123456789]
>>>         WS [0x09,0x0A,0x0D,0x20]
>>>     LPAREN [(]
>>>     RPAREN [)]
>>>      POUND [#]
>>>   ASTERISK [*]     // 0x2a
>>>      COMMA [,]
>>>      SLASH [0x2f]  // "/"
>>>    NEWLINE [0x0A]
>>
>> Why don't you use these last seven? 
>
> I do use them.

I meant why not use them in the code you posted.

> I can refer to either the name or the definition of the character class.
> ASCII and CONTROL may be used in the future.
>
>>>      ASCII [0x20-0x7e]
>>>       ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
>>>      ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
>>>         ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
>>>    CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>
>>> // Recognized Patterns
>>> //
>>> {et} Empty
>>> {ft} Function_Type
>>> {fn} Function_Name
>>> {vt} Variable_Type
>>> {vn} Variable_Name
>>> {fh} Function_Header
>>>
>>> // DFA Definition to recognize C function headers
>>
>> No DFA can do that in general.  You mean "recognise a very restricted
>> subset of C function headers".
>
> It recognizes everything that I will ever write.

Ah.  That simplifies things, and alerts the reader not to check the DFA
since you can just say "I'd never write that!".  However...

>>> // begin of function type
>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)
>>
>> What does that [*] mean?  Judging by the other uses of []s, you seem to
>> be accepting *s and digits at the start of a C function header even
>> though they won't be taken to be one of your named matches.  Why single
>> out *s and digits?
>
> int* M(int* N);

This does not recognise the {fh} pattern.  Putting the named
patterns into the string at the point the action would be triggered I
get

  int* {ft}M({fn}int* {vt}N){vn}

(The ; does not help -- there is no specified transition for ';' is
state 0.)

Furthermore, this example does not explain why you permit digits.  You
say you won't ever write them, but it's odd to permit them where they
are invalid.  That "NUMERIC(00)" part looks like "cargo cult"
programming.

Kept for reference:
>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>
>>> // begin of function name
>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>
>>> // begin of variable type
>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)

>>> // begin of variable name
>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>
>>> // ignores all "//" comments
>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
>>> <13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)
>>>
>>> // look for comment terminator "*/"
>>> <14> ASCII_MINUS_ASTERISK(14) [*](15)
>>> <15>    ASCII_MINUS_SLASH(14) [/](00)
>> 

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#40811 — Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

Fromolcott <NoOne@NoWhere.com>
Date2021-10-25 19:08 -0500
SubjectRe: I finally completed my lexical analyzer generator (needed by my halt decider) update
Message-ID<nPqdnbNMHNB72-r8nZ2dnUU7-S3NnZ2d@giganews.com>
In reply to#40804
On 10/25/2021 6:26 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 10/24/2021 8:08 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> Enhancements: (Assumes that the C source code compiles)
>>>> (a) Ignores /* */ comments
>>>> (b) Ignores #define lines
>>>> (c) Correctly handles trailing space in: int Function_Name(void   )
>>>>
>>>> //
>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>> //  of C function headers.
>>>>
>>>> // Character Classes
>>>> //
>>>>       EMPTY [0]
>>>>       ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>     NUMERIC [0123456789]
>>>>          WS [0x09,0x0A,0x0D,0x20]
>>>>      LPAREN [(]
>>>>      RPAREN [)]
>>>>       POUND [#]
>>>>    ASTERISK [*]     // 0x2a
>>>>       COMMA [,]
>>>>       SLASH [0x2f]  // "/"
>>>>     NEWLINE [0x0A]
>>>
>>> Why don't you use these last seven?
>>
>> I do use them.
> 
> I meant why not use them in the code you posted.

They are used in the DFA shown below.

> 
>> I can refer to either the name or the definition of the character class.
>> ASCII and CONTROL may be used in the future.
>>
>>>>       ASCII [0x20-0x7e]
>>>>        ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
>>>>       ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
>>>>          ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
>>>>     CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>
>>>> // Recognized Patterns
>>>> //
>>>> {et} Empty
>>>> {ft} Function_Type
>>>> {fn} Function_Name
>>>> {vt} Variable_Type
>>>> {vn} Variable_Name
>>>> {fh} Function_Header
>>>>
>>>> // DFA Definition to recognize C function headers
>>>
>>> No DFA can do that in general.  You mean "recognise a very restricted
>>> subset of C function headers".
>>
>> It recognizes everything that I will ever write.
> 
> Ah.  That simplifies things, and alerts the reader not to check the DFA
> since you can just say "I'd never write that!".  However...
> 
If I wanted a more robust function header recognizer I would adapt the 
lex/yacc spec for C.

>>>> // begin of function type
>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)
>>>
>>> What does that [*] mean?  Judging by the other uses of []s, you seem to
>>> be accepting *s and digits at the start of a C function header even
>>> though they won't be taken to be one of your named matches.  Why single
>>> out *s and digits?
>>
>> int* M(int* N);
> 
> This does not recognise the {fh} pattern.  Putting the named
> patterns into the string at the point the action would be triggered I
> get

The above string would be rejected by the C compiler this never reach 
the DFA reogonizer.

> 
>    int* {ft}M({fn}int* {vt}N){vn}
> 
> (The ; does not help -- there is no specified transition for ';' is
> state 0.)
> 
> Furthermore, this example does not explain why you permit digits. 

It recognizes all valid C identifiers.

>  You
> say you won't ever write them, 

I did not say that I will not write digits.
I said that I don't need a full parser.

> but it's odd to permit them where they
> are invalid.  That "NUMERIC(00)" part looks like "cargo cult"
> programming.
> 

It was easiest to write this DFA from scratch when I explicitly 
accounted for all of the character classes on every line.

This line skips white-space
matches the first char of a valid C identifier
ignores asterisk
matches the first char of a C comment
matches the first char of a C #define statement

 >>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)

> Kept for reference:
>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>
>>>> // begin of function name
>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>
>>>> // begin of variable type
>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
> 
>>>> // begin of variable name
>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>
>>>> // ignores all "//" comments
>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
>>>> <13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)
>>>>
>>>> // look for comment terminator "*/"
>>>> <14> ASCII_MINUS_ASTERISK(14) [*](15)
>>>> <15>    ASCII_MINUS_SLASH(14) [/](00)
>>>
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#40835 — Re: I finally completed my lexical analyzer generator (needed by my halt decider) update

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-10-26 02:09 +0100
SubjectRe: I finally completed my lexical analyzer generator (needed by my halt decider) update
Message-ID<87a6iw1tjm.fsf@bsb.me.uk>
In reply to#40811
olcott <NoOne@NoWhere.com> writes:

> On 10/25/2021 6:26 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> On 10/24/2021 8:08 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> Enhancements: (Assumes that the C source code compiles)
>>>>> (a) Ignores /* */ comments
>>>>> (b) Ignores #define lines
>>>>> (c) Correctly handles trailing space in: int Function_Name(void   )
>>>>>
>>>>> //
>>>>> //  Deterministic Finite Automaton (DFA) recognizer
>>>>> //  of C function headers.
>>>>>
>>>>> // Character Classes
>>>>> //
>>>>>       EMPTY [0]
>>>>>       ALPHA [ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz]
>>>>>     NUMERIC [0123456789]
>>>>>          WS [0x09,0x0A,0x0D,0x20]
>>>>>      LPAREN [(]
>>>>>      RPAREN [)]
>>>>>       POUND [#]
>>>>>    ASTERISK [*]     // 0x2a
>>>>>       COMMA [,]
>>>>>       SLASH [0x2f]  // "/"
>>>>>     NEWLINE [0x0A]
>>>>
>>>> Why don't you use these last seven?
>>>
>>> I do use them.
>> I meant why not use them in the code you posted.
>
> They are used in the DFA shown below.

No they are not.

>>> I can refer to either the name or the definition of the character class.
>>> ASCII and CONTROL may be used in the future.
>>>
>>>>>       ASCII [0x20-0x7e]
>>>>>        ASCII_MINUS_NEWLINE [0x00-0x09,0x0b-0x7f]
>>>>>       ASCII_MINUS_ASTERISK [0x00-0x29,0x2b-0x7f]
>>>>>          ASCII_MINUS_SLASH [0x00-0x2e,0x30-0x7f]
>>>>>     CONTROL [0x00-0x09,0x0b-0x1f,0x7f]
>>>>>
>>>>> // Recognized Patterns
>>>>> //
>>>>> {et} Empty
>>>>> {ft} Function_Type
>>>>> {fn} Function_Name
>>>>> {vt} Variable_Type
>>>>> {vn} Variable_Name
>>>>> {fh} Function_Header
>>>>>
>>>>> // DFA Definition to recognize C function headers
>>>>
>>>> No DFA can do that in general.  You mean "recognise a very restricted
>>>> subset of C function headers".
>>>
>>> It recognizes everything that I will ever write.
>>
>> Ah.  That simplifies things, and alerts the reader not to check the DFA
>> since you can just say "I'd never write that!".  However...
>> 
> If I wanted a more robust function header recognizer I would adapt the
> lex/yacc spec for C.

Your DFA does not even recognise the one example you gave!

>>>>> // begin of function type
>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)
>>>>
>>>> What does that [*] mean?  Judging by the other uses of []s, you seem to
>>>> be accepting *s and digits at the start of a C function header even
>>>> though they won't be taken to be one of your named matches.  Why single
>>>> out *s and digits?
>>>
>>> int* M(int* N);
>>
>> This does not recognise the {fh} pattern.  Putting the named
>> patterns into the string at the point the action would be triggered I
>> get
>
> The above string would be rejected by the C compiler this never reach
> the DFA reogonizer.

Don't be silly, of course it won't be rejected.  I thought you knew a
bit about C.  But given that you thought it would be rejected, why give
it as an example or the need to handle *s.

Anyway, even "int f(int x)" does not get recognised as a function
header.  I thought you knew a bit about DFAs.

>>    int* {ft}M({fn}int* {vt}N){vn}
>> (The ; does not help -- there is no specified transition for ';' is
>> state 0.)
>> Furthermore, this example does not explain why you permit digits. 
>
> It recognizes all valid C identifiers.

Do you really not understand the DFA you wrote?  I am asking why you
single out digits to be accepted in state 0.  They form part of
identifiers, but that's not what state 0 is doing.  You skip digits,
spaces and *s in a position where digits are meaning less.

>>  You
>> say you won't ever write them, 
>
> I did not say that I will not write digits.

You said you would not write

  *1*x x(*x x()

and I am asking why you accept digits in state 0.  Why single them out?
They are never valid in that position, but then there are lots of other
characters you could pointlessly accept in state 0 as well.

> I said that I don't need a full parser.
>
>> but it's odd to permit them where they
>> are invalid.  That "NUMERIC(00)" part looks like "cargo cult"
>> programming.
>
> It was easiest to write this DFA from scratch when I explicitly
> accounted for all of the character classes on every line.

Except you don't do that.  You account for some of them in most of the
lines.

> This line skips white-space
> matches the first char of a valid C identifier
> ignores asterisk
> matches the first char of a C comment
> matches the first char of a C #define statement
>
>>>>> <00> WS    (00) ALPHA(01) NUMERIC(00) [*](00) [/](12) [#](13)

and "ignores" digits for some unexplained reason.

>> Kept for reference:
>>>>> <01> WS{ft}(03) ALPHA(01) NUMERIC(01) [*](02)
>>>>> <02> WS{ft}(03) ALPHA(00) NUMERIC(00) [*](02)
>>>>>
>>>>> // begin of function name
>>>>> <03> WS    (03) ALPHA(04) NUMERIC(00) [*](00)
>>>>> <04> WS{fn}(05) ALPHA(04) NUMERIC(04) [*](00) [(]{fn}(06)
>>>>> <05> WS    (05) ALPHA(00) NUMERIC(00) [*](00) [(]    (06)
>>>>>
>>>>> // begin of variable type
>>>>> <06> WS    (06) ALPHA(07) NUMERIC(00) [*](00) [)]{fh}(00)
>>>>> <07> WS{vt}(09) ALPHA(07) NUMERIC(07) [*](08) [)]{fh}(00)
>>>>> <08> WS{vt}(09) ALPHA(00) NUMERIC(00) [*](08)
>> 
>>>>> // begin of variable name
>>>>> <09> WS    (09) ALPHA(10) NUMERIC(00) [*]    (00) [)]{fh}(00)
>>>>> <10> WS{vn}(11) ALPHA(10) NUMERIC(10) [,]{vn}(06) [)]{vn}(00)
>>>>> <11> WS    (11) ALPHA(00) NUMERIC(00) [,]    (06) [)]    (00)
>>>>>
>>>>> // ignores all "//" comments
>>>>> <12> WS     (00) ALPHA(01)  NUMERIC(00) [*](14) [/](13)
>>>>> <13> ASCII_MINUS_NEWLINE(13)  [0x0A] (00)
>>>>>
>>>>> // look for comment terminator "*/"
>>>>> <14> ASCII_MINUS_ASTERISK(14) [*](15)
>>>>> <15>    ASCII_MINUS_SLASH(14) [/](00)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.theory


csiph-web