Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Subject | Re: I finally completed my lexical analyzer generator (needed by my halt decider) |
|---|---|
| Newsgroups | comp.theory |
| References | <TpydnRmO3dkGK-n8nZ2dnUU7-c3NnZ2d@giganews.com> |
| From | Richard Damon <Richard@Damon-Family.org> |
| Message-ID | <mY2dJ.3216$k35.2640@fx33.iad> (permalink) |
| Organization | Forte - www.forteinc.com |
| Date | 2021-10-23 21:49 -0400 |
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.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web