Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: Simply defining Gödel Incompleteness and Tarski Undefinability away V52 (Machine equivalence)
44 views
Skip to first unread message
olcott
Aug 30, 2020, 4:20:16 PM8/30/20
to
On 8/30/2020 3:10 PM, David Kleinecke wrote:
> On Sunday, August 30, 2020 at 12:37:32 PM UTC-7, olcott wrote:
>
>> The equivalence of inputs/outputs is defined as sequences of space
>> delimited binary digits corresponding to the same numerical values as
>> sequences of hexadecimal integers.
>>
>> Equivalent inputs deriving equivalent outputs for all computations
>> define equivalent machines (Turing or otherwise).
>
> You might call this "black box equivalence".
>
Bingo, you got it !!!
> Our data is strings of bits. It is necessary to specify how such
> a string is presented (input) to the box (machine) and how it is
> displayed (output). Given two boxes if for every string the outputs
> are the same for both boxes then there is black box equivalence.
> But the contents of the two boxes may well differ.
>
> In order to define the IO we might use quipus - real world strings
> with knots tied in them. We drop a quipu into the box, the box hums
> for a while and then lays another quipu.
>
> Note the implication that the machine always halts.
>
> We cannot say that two boxes that both never halt for some input
> have the same output for that input.
>
Or we could construe not halting as an empty set of output. As long as
the two machines produced equivalent output when they halted or failed
to halt on equivalent input the two machines are black box equivalent.
--
Copyright 2020 Pete Olcott
> On Sunday, August 30, 2020 at 12:37:32 PM UTC-7, olcott wrote:
>
>> The equivalence of inputs/outputs is defined as sequences of space
>> delimited binary digits corresponding to the same numerical values as
>> sequences of hexadecimal integers.
>>
>> Equivalent inputs deriving equivalent outputs for all computations
>> define equivalent machines (Turing or otherwise).
>
> You might call this "black box equivalence".
>
Bingo, you got it !!!
> Our data is strings of bits. It is necessary to specify how such
> a string is presented (input) to the box (machine) and how it is
> displayed (output). Given two boxes if for every string the outputs
> are the same for both boxes then there is black box equivalence.
> But the contents of the two boxes may well differ.
>
> In order to define the IO we might use quipus - real world strings
> with knots tied in them. We drop a quipu into the box, the box hums
> for a while and then lays another quipu.
>
> Note the implication that the machine always halts.
>
> We cannot say that two boxes that both never halt for some input
> have the same output for that input.
>
Or we could construe not halting as an empty set of output. As long as
the two machines produced equivalent output when they halted or failed
to halt on equivalent input the two machines are black box equivalent.
--
Copyright 2020 Pete Olcott
olcott
Aug 30, 2020, 8:18:19 PM8/30/20
to
On 8/30/2020 6:23 PM, Andy Walker wrote:
> in general. Halting problem. You don't know how long to wait to
Yes that is why a refutation of the conventional self-referential
halting problem proofs would be significant.
> find out if they could halt. Busy Beaver problem. You don't know
> whether two machines are equivalent, black box or otherwise. *If*
> you know that both machines halt, *then* you can find out whether
> they are equivalent. If the machines are equivalent on some input,
> you don't know whether they are equivalent on other inputs. Since
That two machines always derive equivalent output from equivalent input
and fail to halt on the same inputs proves that these two machines are
equivalent.
We may also know that two machines are equivalent on all inputs if each
machine can simulate the other.
> some very small TMs are UTMs, even quite short C programs [eg] are
> completely inscrutable, in general, given arbitrary data.
>
> If you want to know things about programs, then you have to
> write them in such a way that theorems about them can be proved.
I only need to prove that certain computations that halt on specific
inputs are equivalent to a Turing machine on equivalent input.
My whole goal here is to prove that a halt decider written in "C" that
analyzes the x86 machine language of itself could be directly applied to
Turing machines.
> Then you may be able to say interesting things about programs that
> conform to your specification. Otherwise the future is somewhat
> bleak.
>
Any virtual machine that implements an abstract model of computation
that is provably Turing equivalent will have identical computation to
any concrete hardware implementation of this abstract model until a
computation on this concrete model requires more RAM than it has.
In simpler words a program written in the virtual machine language will
run exactly the same (identical execution trace) on the abstract machine
as the concrete machine unless and until the concrete machine runs out
of RAM.
If we did not hit the RAM limit then we know that the execution of the
program on concrete machine would be equivalent to executing an
equivalent program on an actual Turing machine.
Every "C" language program that can be translated into the machine
language of any virtual machine that is provably Turing equivalent would
derive equivalent output to equivalent input on an actual Turing machine.
This establishes the basis of the line-of-reasoning showing that my
intuition that "C" programs always have been equivalent to Turing
machines is probably correct.
The above possibly creates a new term-of-the-art of computer science, a
Turing equivalent computation:
A Turing equivalent computation is any computation that can be
translated into the machine language of any virtual machine that is
provably Turing equivalent.
> Note that the programs that control autonomous vehicles,
> nuclear power stations, ..., though usually much more carefully
> written than the average student project, are, in the present
> state of technology, in the bleak/inscrutable set rather than
> the interesting set. The "comp.risks" newsgroup is full of the
> consequences of such bleakness, and should be read by every
> computer professional. But it isn't, and won't be, so lessons
> are learned after disasters rather than before. We live in a
> more dangerous world as a consequence, for all the benefits that
> computers have brought. Enjoy!
> On 30/08/2020 21:19, olcott wrote:
>> Or we could construe not halting as an empty set of output. As long
>> as the two machines produced equivalent output when they halted or
>> failed to halt on equivalent input the two machines are black box
>> equivalent.
>
> You don't know that the machines are going to fail to halt,
>> Or we could construe not halting as an empty set of output. As long
>> as the two machines produced equivalent output when they halted or
>> failed to halt on equivalent input the two machines are black box
>> equivalent.
>
> in general. Halting problem. You don't know how long to wait to
Yes that is why a refutation of the conventional self-referential
halting problem proofs would be significant.
> find out if they could halt. Busy Beaver problem. You don't know
> whether two machines are equivalent, black box or otherwise. *If*
> you know that both machines halt, *then* you can find out whether
> they are equivalent. If the machines are equivalent on some input,
> you don't know whether they are equivalent on other inputs. Since
That two machines always derive equivalent output from equivalent input
and fail to halt on the same inputs proves that these two machines are
equivalent.
We may also know that two machines are equivalent on all inputs if each
machine can simulate the other.
> some very small TMs are UTMs, even quite short C programs [eg] are
> completely inscrutable, in general, given arbitrary data.
>
> If you want to know things about programs, then you have to
> write them in such a way that theorems about them can be proved.
I only need to prove that certain computations that halt on specific
inputs are equivalent to a Turing machine on equivalent input.
My whole goal here is to prove that a halt decider written in "C" that
analyzes the x86 machine language of itself could be directly applied to
Turing machines.
> Then you may be able to say interesting things about programs that
> conform to your specification. Otherwise the future is somewhat
> bleak.
>
Any virtual machine that implements an abstract model of computation
that is provably Turing equivalent will have identical computation to
any concrete hardware implementation of this abstract model until a
computation on this concrete model requires more RAM than it has.
In simpler words a program written in the virtual machine language will
run exactly the same (identical execution trace) on the abstract machine
as the concrete machine unless and until the concrete machine runs out
of RAM.
If we did not hit the RAM limit then we know that the execution of the
program on concrete machine would be equivalent to executing an
equivalent program on an actual Turing machine.
Every "C" language program that can be translated into the machine
language of any virtual machine that is provably Turing equivalent would
derive equivalent output to equivalent input on an actual Turing machine.
This establishes the basis of the line-of-reasoning showing that my
intuition that "C" programs always have been equivalent to Turing
machines is probably correct.
The above possibly creates a new term-of-the-art of computer science, a
Turing equivalent computation:
A Turing equivalent computation is any computation that can be
translated into the machine language of any virtual machine that is
provably Turing equivalent.
> Note that the programs that control autonomous vehicles,
> nuclear power stations, ..., though usually much more carefully
> written than the average student project, are, in the present
> state of technology, in the bleak/inscrutable set rather than
> the interesting set. The "comp.risks" newsgroup is full of the
> consequences of such bleakness, and should be read by every
> computer professional. But it isn't, and won't be, so lessons
> are learned after disasters rather than before. We live in a
> more dangerous world as a consequence, for all the benefits that
> computers have brought. Enjoy!
Richard Damon
Aug 30, 2020, 8:44:12 PM8/30/20
to
some arbitrary period of time more that neither of them might halt. Any
definition based on comparing the outputs at some finite time is
incomplete, and possibly inaccurate.
olcott
Aug 30, 2020, 9:21:55 PM8/30/20
to
both machines have halted would be correct for the computations that
result in halting.
olcott
Aug 31, 2020, 9:47:24 AM8/31/20
to
On 8/31/2020 3:59 AM, Andy Walker wrote:
> On 31/08/2020 01:17, olcott wrote:
> [I wrote:]
> not hold your breath.
glance at a few word before forming you rebuttal.
On 8/30/2020 7:17 PM, olcott wrote:
> We may also know that two machines are equivalent on all
> inputs if each machine can simulate the other.
The easy way to know that a machine is Turing equivalent is to start
with a Turing machine and then only add features to this exact same
model of computation that make it easier to work with and not have more
computational power. If you mess up and add computational power then
this "mistake" refutes Church-Turing.
> It would, but there is no effective general method to show
> that. You're going round in circles. But we knew that.
>
You ignored the way to show that reiterated above.
> On 31/08/2020 01:17, olcott wrote:
> [I wrote:]
>>> You don't know that the machines are going to fail to halt,
>>> in general. Halting problem. You don't know how long to wait to
>> Yes that is why a refutation of the conventional self-referential
>> halting problem proofs would be significant.
>
> It would be more than significant, it would be amazing. Do
>>> in general. Halting problem. You don't know how long to wait to
>> Yes that is why a refutation of the conventional self-referential
>> halting problem proofs would be significant.
>
> not hold your breath.
>
>> That two machines always derive equivalent output from equivalent
>> input and fail to halt on the same inputs proves that these two
>> machines are equivalent.
>
That is why you have to read everything that I said and not merely
>> That two machines always derive equivalent output from equivalent
>> input and fail to halt on the same inputs proves that these two
>> machines are equivalent.
>
glance at a few word before forming you rebuttal.
On 8/30/2020 7:17 PM, olcott wrote:
> We may also know that two machines are equivalent on all
> inputs if each machine can simulate the other.
with a Turing machine and then only add features to this exact same
model of computation that make it easier to work with and not have more
computational power. If you mess up and add computational power then
this "mistake" refutes Church-Turing.
> It would, but there is no effective general method to show
> that. You're going round in circles. But we knew that.
>
You ignored the way to show that reiterated above.
olcott
Sep 3, 2020, 11:02:55 PM9/3/20
to
On 9/3/2020 8:50 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> I now have the every single detailed design of an x86 virtual machine
>> that matches the self-referential aspect of the H_Hat template (and
>> all of the conventional HP proofs) such that this virtual machine
>> correctly decides halting on itself and this computation is equivalent
>> to a Turing machine computation.
>
> You are going backwards. 20 months after having every detail fully
> encoded as actual Turing machines, you now only have a design. At this
> rate, in another 20 months, you will have a blank piece of paper.
>
> And you don't have to show Turing completeness or equivalence. All of
> that is a red herring
No it was proactively eliminating the basis for rejection.
I wanted to eliminate the possibility that I would have to spent another
two years convincing people that my works applies to Turing Machines.
> because your claim (at least the only interesting
> bit of your claim) is about one computation (in my notation P(<[P^],
> [P^]>)), and that one computation halts (it must do or it can't give an
> answer, correct or otherwise). A single halting computation (whether
> written as a TM or in x86 code, Fortran, C anything else) can never
> require more than a finite quantity of memory. You don't need an
> unbounded model for one finite computation.
Yes now lets make sure we totally describe that completely using all the
right terms of the art. When I describe the gist of what I have so that
this gist can be easily understood you always tear it apart on what
seems to me to be nit-picky trivialities.
Basically what I have is code that matches the Linz H-hat template in
that it presents halt deciders with the conventional self-referential
seemingly impossible case. It only matches this aspect of the Linz
template. http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
I implemented this code to be equivalent to a UTM with the exception of
unlimited memory. It is well known in the field that RASP machines are
Turing equivalent and equivalent to UTMs,
I did it this way to eliminate the tedious dichotomy of a machine and
its description. The x86 machine code is both the machine and its
description. H_Hat can both examine itself and execute itself in
debug-step mode. H_Hat can also correctly decide halting for many other
x86 programs.
It was designed so that it can provide correct yes or no answers to
whether it halts on itself as input. The 2018 implementation was very
brittle it could only decide a single instance of itself. The latest
design is much more robust. I could add this much great robustness with
very little extra coding.
>
> It all just delaying tactics to avoid having to post anything. You know
> the boasting party will be over when you have to publish, so you will
> delay for as long as you possibly can. That's probably going to be
> years, isn't it?
>
No. The Master UTM equivalent is almost done. I have been working on it
for many months at least 60 hours per week. The master UTM may be ready
for review next week. There might be another delay in getting it to work
on Linux again. I may eventually implement it as a web-service.
Once all the infrastructure is in place implementing the: (every single
step of design is already complete) halting code will be nearly trivial.
> olcott <No...@NoWhere.com> writes:
>
>> I now have the every single detailed design of an x86 virtual machine
>> that matches the self-referential aspect of the H_Hat template (and
>> all of the conventional HP proofs) such that this virtual machine
>> correctly decides halting on itself and this computation is equivalent
>> to a Turing machine computation.
>
> You are going backwards. 20 months after having every detail fully
> encoded as actual Turing machines, you now only have a design. At this
> rate, in another 20 months, you will have a blank piece of paper.
>
> And you don't have to show Turing completeness or equivalence. All of
> that is a red herring
No it was proactively eliminating the basis for rejection.
I wanted to eliminate the possibility that I would have to spent another
two years convincing people that my works applies to Turing Machines.
> because your claim (at least the only interesting
> bit of your claim) is about one computation (in my notation P(<[P^],
> [P^]>)), and that one computation halts (it must do or it can't give an
> answer, correct or otherwise). A single halting computation (whether
> written as a TM or in x86 code, Fortran, C anything else) can never
> require more than a finite quantity of memory. You don't need an
> unbounded model for one finite computation.
Yes now lets make sure we totally describe that completely using all the
right terms of the art. When I describe the gist of what I have so that
this gist can be easily understood you always tear it apart on what
seems to me to be nit-picky trivialities.
Basically what I have is code that matches the Linz H-hat template in
that it presents halt deciders with the conventional self-referential
seemingly impossible case. It only matches this aspect of the Linz
template. http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
I implemented this code to be equivalent to a UTM with the exception of
unlimited memory. It is well known in the field that RASP machines are
Turing equivalent and equivalent to UTMs,
I did it this way to eliminate the tedious dichotomy of a machine and
its description. The x86 machine code is both the machine and its
description. H_Hat can both examine itself and execute itself in
debug-step mode. H_Hat can also correctly decide halting for many other
x86 programs.
It was designed so that it can provide correct yes or no answers to
whether it halts on itself as input. The 2018 implementation was very
brittle it could only decide a single instance of itself. The latest
design is much more robust. I could add this much great robustness with
very little extra coding.
>
> It all just delaying tactics to avoid having to post anything. You know
> the boasting party will be over when you have to publish, so you will
> delay for as long as you possibly can. That's probably going to be
> years, isn't it?
>
No. The Master UTM equivalent is almost done. I have been working on it
for many months at least 60 hours per week. The master UTM may be ready
for review next week. There might be another delay in getting it to work
on Linux again. I may eventually implement it as a web-service.
Once all the infrastructure is in place implementing the: (every single
step of design is already complete) halting code will be nearly trivial.
Jeff Barnett
Sep 4, 2020, 12:44:27 AM9/4/20
to
On 9/3/2020 9:02 PM, olcott wrote:
> No. The Master UTM equivalent is almost done. I have been working on it
> for many months at least 60 hours per week. The master UTM may be ready
> for review next week. There might be another delay in getting it to work
> on Linux again. I may eventually implement it as a web-service.
Nonsense! Let's add it up per week:
> No. The Master UTM equivalent is almost done. I have been working on it
> for many months at least 60 hours per week. The master UTM may be ready
> for review next week. There might be another delay in getting it to work
> on Linux again. I may eventually implement it as a web-service.
60 hours coding an insufficient and impossible program;
an average of 20 emails per day at 15 minutes per msg is 35 hours per week;
time to recall previous lies and mistakes and plan to not expose your
back side to more humiliation is about 3 hours a week;
average of 3 new quotes per day of undigested material at 15 minutes per
is 5+ hours a week;
time to celebrate if a troll or recover from humiliation if a pseudo
philosopher is about 30 minutes per day and 3+ hours per week;
an average of 1 hour a day to procure food, prepare it, then consume it
is 7 hours a week;
time to work on your {G|g}od blog is 3 hours a week;
time to brush teeth, shower, etc. 3+ hours a week;
assuming you aren't completely constipated, 3 hours a week in front of
or on the throne;
average time to pay bills, renew insurance, etc. is 3 hours per week;
tidy up your place, do or submit your laundry, take out the garbage,
etc. averages 3 hours a week.
-------------------------------------------------------------------
I think the above comes to 122 hours a week leaving 22 hours or 3 hours
a day for sleep. I assume that you don't have a pet, a live in person
with whom you interact, or any hobbies. If any of these assumptions are
false, there's even less sleep.
--
Jeff Barnett
red floyd
Sep 4, 2020, 2:10:02 PM9/4/20
to
On 9/3/2020 9:44 PM, Jeff Barnett wrote:
[redacted]
just over 6 hours to sleep, and do anything else.
[redacted]
> -------------------------------------------------------------------
> I think the above comes to 122 hours a week leaving 22 hours or 3 hours
> a day for sleep. I assume that you don't have a pet, a live in person
> with whom you interact, or any hobbies. If any of these assumptions are
> false, there's even less sleep.
Minor math error. There are 168 hours in a week. 168-122 = 46. He has
> I think the above comes to 122 hours a week leaving 22 hours or 3 hours
> a day for sleep. I assume that you don't have a pet, a live in person
> with whom you interact, or any hobbies. If any of these assumptions are
> false, there's even less sleep.
just over 6 hours to sleep, and do anything else.
olcott
Sep 4, 2020, 2:34:44 PM9/4/20
to
my x86 based UTM equivalent I spent at least twelve hours per day six
days per week and only 8 hours on my day of rest.
I usually get between 7 and 8 hours per night of sleep, I take many
short-cuts to greatly reduce the other normal daily chores. For example
daily food preparation takes about two minutes per five small meals.
Roasting a chicken once per week takes less that 30 minutes of labor
including packaging the portions. Grocery shopping is point and click.
olcott
Sep 5, 2020, 1:40:41 AM9/5/20
to
On 9/4/2020 11:50 PM, André G. Isaak wrote:
> On 2020-09-04 19:58, olcott wrote:
>
>> If I provide code that is equivalent to H that correctly decides
>> halting for code that is equivalent to H_Hat I will have proved my point.
>
> How exactly do you propose to provide code that is 'equivalent to H'
> given that Linz doesn't actually provide a description of H? H is a
> purely hypothetical TM which is claimed to decide halting for every
> possible input but whose workings are not described.
>
> André
>
Linz provides a very simple state machine definition of H.
It has one start state (q0) and two final states ((qy)) and ((qn))
having a wildcard state transitions in-between.
The H_Hat variation merely prepends a well defined state (copy input)
and appends a pair of infinite loop states.
The key unspecified aspect of these machines is the transition from (q0)
to (qy) or (qn). Everything else is totally specified.
These wildcard state transitions essentially allow any computation that
gets the right answer. This all boils down to anything that I specify
that gets the right answer in-between (q0) and (qy) or (qn) counts as
valid.
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
> On 2020-09-04 19:58, olcott wrote:
>
>> If I provide code that is equivalent to H that correctly decides
>> halting for code that is equivalent to H_Hat I will have proved my point.
>
> How exactly do you propose to provide code that is 'equivalent to H'
> given that Linz doesn't actually provide a description of H? H is a
> purely hypothetical TM which is claimed to decide halting for every
> possible input but whose workings are not described.
>
> André
>
Linz provides a very simple state machine definition of H.
It has one start state (q0) and two final states ((qy)) and ((qn))
having a wildcard state transitions in-between.
The H_Hat variation merely prepends a well defined state (copy input)
and appends a pair of infinite loop states.
The key unspecified aspect of these machines is the transition from (q0)
to (qy) or (qn). Everything else is totally specified.
These wildcard state transitions essentially allow any computation that
gets the right answer. This all boils down to anything that I specify
that gets the right answer in-between (q0) and (qy) or (qn) counts as
valid.
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
olcott
Sep 5, 2020, 3:16:59 PM9/5/20
to
On 9/5/2020 1:33 PM, André G. Isaak wrote:
> On 2020-09-05 12:17, olcott wrote:
>> On 9/5/2020 12:42 PM, André G. Isaak wrote:
>>> On 2020-09-05 11:12, olcott wrote:
>>>> On 9/5/2020 11:40 AM, André G. Isaak wrote:
>>>>> On 2020-09-05 10:20, olcott wrote:
>>>>>
>>>>>> All that I can say is that H does correctly decide halting for at
>>>>>> least one instance of H_Hat.
>>>>> What exactly do you mean by "at least one instance" of Ĥ?
>>>>>
>>>>> For any given H, there is only a single Ĥ given that Ĥ is derived
>>>>> from H. So your "halt decider" in its final form, call it PO, will
>>>>> determine exactly what PÔ will be. That's the only "instance" that
>>>>> actually matters.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> I recently created the idea of Turing equivalent computations that is
>>>> distinctly different than Turing equivalent machines.
>>>>
>>>> The set of Turing equivalent computations is defined to have the
>>>> following properties:
>>>>
>>>> Turing equivalent computations derive equivalent output or fail to
>>>> halt on equivalent input between the concrete machine and its Turing
>>>> machine equivalent.
>>>>
>>>> Turing equivalent computations are finite computations such that
>>>> they require no more memory than the concrete machine actually has.
>>>>
>>>> Because conventional x86/x64/C programs map to an adaptation of the
>>>> RASP model of computation and the RASP model of computation is known
>>>> to be equivalent to a Turing machine we can know that x86/x64/C
>>>> programs requiring no more memory than they have would have
>>>> equivalent behavior on a Turing machine.
>>>
>>> None of the above relates to my question.
>>>
>>>> A single Turing equivalent computation of a program matching the
>>>> Peter Linz H/H_Hat templates (for this single computation) such that
>>>> H correctly decides halting on H_Hat refutes the Peter Linz proof.
>>>>
>>>> It has to be a decider in the unconventional sense in that it has to
>>>> show the steps proving that its Boolean answer is correct. It can
>>>> only do this when at least one instance of the H/H_Hat computation
>>>> is concretely defined.
>>>
>>> Again, what do you mean by "at least one instance"?
>>>
>>> Whatever your x86 program is, that gets to be H in Linz's proof. Ĥ
>>> therefore must be derived from *your* x86 program in exactly the same
>>> way that Linz derives his Ĥ from his H (except, of course, that it
>>> would use loops based on x86 rather than on state transitions). That
>>> means that there is only a single "instance" of Ĥ which of interest
>>> as far as your program is concerned. Hence my confusion regarding
>>> your use of "at least one instance".
>>>
>>
>> Re-read my definition of Turing equivalent computation again and again
>> until you get it.
>
> Nothing in your definition mentions anything about "instances". I'm
> asking you to explain what you mean by "at least one instance".
It is analogous to usage in OOP between a class
and an instance of a class.
Linz H
(q0)---->(HDC)---->((qy)) or ((qn))
based on some halting deciding code in (HDC).
Linz Ĥ
(q0)---->(qx)---->(HDX)---->(qy)---->(infinite_loop) or ((qn))
based on same halting deciding code in (HDC).
As long as the halt deciding code in HDC is the same in H and H_Hat and
shows that its decision is correct then the Linz proof has been refuted.
I don't have to show that H can correctly decide halting for every
possible encoding of the halting code. I only have to show that it is
not the H / H_hat template that prevents a correct halting decision.
When I do this then every conventional self-referential halting problem
counter-example will have been refuted along with the only basis of all
of these proofs.
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.
> On 2020-09-05 12:17, olcott wrote:
>> On 9/5/2020 12:42 PM, André G. Isaak wrote:
>>> On 2020-09-05 11:12, olcott wrote:
>>>> On 9/5/2020 11:40 AM, André G. Isaak wrote:
>>>>> On 2020-09-05 10:20, olcott wrote:
>>>>>
>>>>>> All that I can say is that H does correctly decide halting for at
>>>>>> least one instance of H_Hat.
>>>>> What exactly do you mean by "at least one instance" of Ĥ?
>>>>>
>>>>> For any given H, there is only a single Ĥ given that Ĥ is derived
>>>>> from H. So your "halt decider" in its final form, call it PO, will
>>>>> determine exactly what PÔ will be. That's the only "instance" that
>>>>> actually matters.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> I recently created the idea of Turing equivalent computations that is
>>>> distinctly different than Turing equivalent machines.
>>>>
>>>> The set of Turing equivalent computations is defined to have the
>>>> following properties:
>>>>
>>>> Turing equivalent computations derive equivalent output or fail to
>>>> halt on equivalent input between the concrete machine and its Turing
>>>> machine equivalent.
>>>>
>>>> Turing equivalent computations are finite computations such that
>>>> they require no more memory than the concrete machine actually has.
>>>>
>>>> Because conventional x86/x64/C programs map to an adaptation of the
>>>> RASP model of computation and the RASP model of computation is known
>>>> to be equivalent to a Turing machine we can know that x86/x64/C
>>>> programs requiring no more memory than they have would have
>>>> equivalent behavior on a Turing machine.
>>>
>>> None of the above relates to my question.
>>>
>>>> A single Turing equivalent computation of a program matching the
>>>> Peter Linz H/H_Hat templates (for this single computation) such that
>>>> H correctly decides halting on H_Hat refutes the Peter Linz proof.
>>>>
>>>> It has to be a decider in the unconventional sense in that it has to
>>>> show the steps proving that its Boolean answer is correct. It can
>>>> only do this when at least one instance of the H/H_Hat computation
>>>> is concretely defined.
>>>
>>> Again, what do you mean by "at least one instance"?
>>>
>>> Whatever your x86 program is, that gets to be H in Linz's proof. Ĥ
>>> therefore must be derived from *your* x86 program in exactly the same
>>> way that Linz derives his Ĥ from his H (except, of course, that it
>>> would use loops based on x86 rather than on state transitions). That
>>> means that there is only a single "instance" of Ĥ which of interest
>>> as far as your program is concerned. Hence my confusion regarding
>>> your use of "at least one instance".
>>>
>>
>> Re-read my definition of Turing equivalent computation again and again
>> until you get it.
>
> Nothing in your definition mentions anything about "instances". I'm
> asking you to explain what you mean by "at least one instance".
It is analogous to usage in OOP between a class
and an instance of a class.
Linz H
(q0)---->(HDC)---->((qy)) or ((qn))
based on some halting deciding code in (HDC).
Linz Ĥ
(q0)---->(qx)---->(HDX)---->(qy)---->(infinite_loop) or ((qn))
based on same halting deciding code in (HDC).
As long as the halt deciding code in HDC is the same in H and H_Hat and
shows that its decision is correct then the Linz proof has been refuted.
I don't have to show that H can correctly decide halting for every
possible encoding of the halting code. I only have to show that it is
not the H / H_hat template that prevents a correct halting decision.
When I do this then every conventional self-referential halting problem
counter-example will have been refuted along with the only basis of all
of these proofs.
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.
Richard Damon
Sep 5, 2020, 4:19:50 PM9/5/20
to
On 9/5/20 3:16 PM, olcott wrote:
>
> As long as the halt deciding code in HDC is the same in H and H_Hat and
> shows that its decision is correct then the Linz proof has been refuted.
And how do you show the answer is correct when it is always wrong by
>
> As long as the halt deciding code in HDC is the same in H and H_Hat and
> shows that its decision is correct then the Linz proof has been refuted.
definition?
If the HDC determines that H_Hat WILL halt, then H_Hat, by its
definition needs to infinitely loop, so the determination that it will
halt is incorrect.
If the HDC determines that H_Hat will not halt, then H_Hat, by its
definition needs to halt, then the determination that it will not halt
is incorrect.
If the HDC does not determine what will happen, it violates its
requirement as a HDC, and is thus incorrect.
olcott
Sep 5, 2020, 4:31:35 PM9/5/20
to
On 9/5/2020 3:19 PM, Richard Damon wrote:
> On 9/5/20 3:16 PM, olcott wrote:
>>
>> As long as the halt deciding code in HDC is the same in H and H_Hat and
>> shows that its decision is correct then the Linz proof has been refuted.
>
> And how do you show the answer is correct when it is always wrong by
> definition?
>
When we actually see H correctly deciding an instance of H_Hat we find
> On 9/5/20 3:16 PM, olcott wrote:
>>
>> As long as the halt deciding code in HDC is the same in H and H_Hat and
>> shows that its decision is correct then the Linz proof has been refuted.
>
> And how do you show the answer is correct when it is always wrong by
> definition?
>
that prior understanding of the Halting Problem as impossible by
definition is an incorrect understanding.
> If the HDC determines that H_Hat WILL halt, then H_Hat, by its
> definition needs to infinitely loop, so the determination that it will
> halt is incorrect.
>
> If the HDC determines that H_Hat will not halt, then H_Hat, by its
> definition needs to halt, then the determination that it will not halt
> is incorrect.
>
> If the HDC does not determine what will happen, it violates its
> requirement as a HDC, and is thus incorrect.
>
Richard Damon
Sep 5, 2020, 5:19:57 PM9/5/20
to
On 9/5/20 4:31 PM, olcott wrote:
> On 9/5/2020 3:19 PM, Richard Damon wrote:
>> On 9/5/20 3:16 PM, olcott wrote:
>>>
>>> As long as the halt deciding code in HDC is the same in H and H_Hat and
>>> shows that its decision is correct then the Linz proof has been refuted.
>>
>> And how do you show the answer is correct when it is always wrong by
>> definition?
>>
>
> When we actually see H correctly deciding an instance of H_Hat we find
> that prior understanding of the Halting Problem as impossible by
> definition is an incorrect understanding.
So what does your machine do????
> On 9/5/2020 3:19 PM, Richard Damon wrote:
>> On 9/5/20 3:16 PM, olcott wrote:
>>>
>>> As long as the halt deciding code in HDC is the same in H and H_Hat and
>>> shows that its decision is correct then the Linz proof has been refuted.
>>
>> And how do you show the answer is correct when it is always wrong by
>> definition?
>>
>
> When we actually see H correctly deciding an instance of H_Hat we find
> that prior understanding of the Halting Problem as impossible by
> definition is an incorrect understanding.
I suspect, fail to meet the requirements.
>
>> If the HDC determines that H_Hat WILL halt, then H_Hat, by its
>> definition needs to infinitely loop, so the determination that it will
>> halt is incorrect.
>>
>> If the HDC determines that H_Hat will not halt, then H_Hat, by its
>> definition needs to halt, then the determination that it will not halt
>> is incorrect.
>>
>> If the HDC does not determine what will happen, it violates its
>> requirement as a HDC, and is thus incorrect.
>>
>
> There is a loophole.
>
>
Only by redefining that you are solving a different problem using (I
>> If the HDC determines that H_Hat WILL halt, then H_Hat, by its
>> definition needs to infinitely loop, so the determination that it will
>> halt is incorrect.
>>
>> If the HDC determines that H_Hat will not halt, then H_Hat, by its
>> definition needs to halt, then the determination that it will not halt
>> is incorrect.
>>
>> If the HDC does not determine what will happen, it violates its
>> requirement as a HDC, and is thus incorrect.
>>
>
> There is a loophole.
>
>
suppose) some other fundamental axioms of logic. I hope that you have
fully examined your new axioms that you are working on.
If you REALLY have a loophole in the proof, because the proof is so
simple, the loophole should have a fairly simple description. A wildly
complicated counter is certainly going to be like the proofs of 1 == 2
that rely on hiding a division by 0 in them.
My guess is you have missed some characteristic of true Turing Machines
(which can't physically exist as they have potentially infinite memory).
It is well known that the Halting problem CAN be solved for a memory
limited Turing Machine, even by another memory limited (but much bigger
memory) Turing Machine.
My first guess is either you have that sort of flaw, or you are failing
to provide the answer in true Finite time.
André G. Isaak
Sep 5, 2020, 5:29:20 PM9/5/20
to
On 2020-09-05 13:16, olcott wrote:
> On 9/5/2020 1:33 PM, André G. Isaak wrote:
>> On 2020-09-05 12:17, olcott wrote:
>>> Re-read my definition of Turing equivalent computation again and
>>> again until you get it.
>>
>> Nothing in your definition mentions anything about "instances". I'm
>> asking you to explain what you mean by "at least one instance".
>
> It is analogous to usage in OOP between a class
> and an instance of a class.
I don't see the analogy. Nor do I see how it relates to your definition
> On 9/5/2020 1:33 PM, André G. Isaak wrote:
>> On 2020-09-05 12:17, olcott wrote:
>>> Re-read my definition of Turing equivalent computation again and
>>> again until you get it.
>>
>> Nothing in your definition mentions anything about "instances". I'm
>> asking you to explain what you mean by "at least one instance".
>
> It is analogous to usage in OOP between a class
> and an instance of a class.
of Turing equivalent computation.
> Linz H
> (q0)---->(HDC)---->((qy)) or ((qn))
> based on some halting deciding code in (HDC).
>
> Linz Ĥ
> (q0)---->(qx)---->(HDX)---->(qy)---->(infinite_loop) or ((qn))
> based on same halting deciding code in (HDC).
André
--
To email remove 'invalid' & replace 'gm' with well known Google mail
service.
André G. Isaak
Sep 5, 2020, 5:29:59 PM9/5/20
to
André G. Isaak
Sep 5, 2020, 5:52:43 PM9/5/20
to
On 2020-09-05 14:31, olcott wrote:
> On 9/5/2020 3:19 PM, Richard Damon wrote:
>> On 9/5/20 3:16 PM, olcott wrote:
>>>
>>> As long as the halt deciding code in HDC is the same in H and H_Hat and
>>> shows that its decision is correct then the Linz proof has been refuted.
>>
>> And how do you show the answer is correct when it is always wrong by
>> definition?
>>
>
> When we actually see H correctly deciding an instance of H_Hat we find
> that prior understanding of the Halting Problem as impossible by
> definition is an incorrect understanding.
Since you claim to have have had your solution "fully encoded" at one
>> On 9/5/20 3:16 PM, olcott wrote:
>>>
>>> As long as the halt deciding code in HDC is the same in H and H_Hat and
>>> shows that its decision is correct then the Linz proof has been refuted.
>>
>> And how do you show the answer is correct when it is always wrong by
>> definition?
>>
>
> When we actually see H correctly deciding an instance of H_Hat we find
> that prior understanding of the Halting Problem as impossible by
> definition is an incorrect understanding.
time, then you should be able to answer the following very simple question:
When given your <Ĥ, Ĥ> as input, does your program claim that this halts
or that it doesn't halt. No need to provide any details of how it
arrives at the answer -- you can continue to keep that secret -- I just
want to know what answer it actually gives.
Mike Terry
Sep 5, 2020, 6:02:14 PM9/5/20
to
H (the decider) and H_Hat (the test case). Either his H_Hat will be
wildly off in relationship to H, or the correspondence will be broken in
some more subtle (but not that subtle!) way. E.g. he could "cheat"
through H being passed some kind of hidden input other than its
legitimate input (H^Hat, H_Hat), enabling it to behave differently when
it's invoked internally within H_Hat. (Input from global variables?
Something in his emulator implementation? ...)
But he's not going to give any details, so we'll just have to wait and
see...
Mike.
Jeff Barnett
Sep 5, 2020, 7:52:35 PM9/5/20
to
mistakes unless utterly by accident. Also there is a lot of troll in him
and the only detectable trait is that he wants people to respond to his
inanities. Just remember that he claimed to have all of this ready to
go, i.e. coded, around two years ago - lies of course - and this is all
a rearguard action to cover his ego. In other, words don't expect to
ever see a TM or equivalent encoding for H.
> But he's not going to give any details, so we'll just have to wait and
> see...
Jeff Barnett
Richard Damon
Sep 5, 2020, 9:12:39 PM9/5/20
to
that is good enough to be considered as the 'Not Halting' answer, when
of course it isn't. That or some other 'small' change to the ground
rules, that would actually allow H to be something trivial or
uninteresting, so proving that this modified H can exist actully means
nothing.
olcott
Sep 5, 2020, 10:50:15 PM9/5/20
to
Linz H
(q0)---->(HDC)---->((qy)) or ((qn))
based on some halting deciding code in (HDC).
Linz Ĥ
(q0)---->(qx)---->(HDC)---->(qy)---->(infinite_loop) or ((qn))
(q0)---->(HDC)---->((qy)) or ((qn))
based on some halting deciding code in (HDC).
Linz Ĥ
based on same halting deciding code in (HDC).
As long as the halt deciding code in HDC is the same in H and H_Hat and
shows that its decision is correct then the Linz proof has been refuted.
The halting code is the only unspecified detail of H or Ĥ.
shows that its decision is correct then the Linz proof has been refuted.
I make sure that the halting code is the same in H and Ĥ by having them
both call the same function.
I don't have to show that H can correctly decide halting for every
possible encoding of the halting code. I only have to show that it is
not the H / H_hat template that prevents a correct halting decision.
Mike Terry
Sep 5, 2020, 11:35:42 PM9/5/20
to
H decides (Ĥ, Ĥ) must be the same as the input to the embedded copy of H
within Ĥ when Ĥ runs with input (Ĥ). That should essentially be
guaranteed by the coding of Ĥ assuming it is correctly related to H, but
also the embedded H cannot receive any "hidden" input from global
variables or elsewhere. (This can't happen with a TM, as input is
exactly what is on the tape and nothing more, and that is precisely (Ĥ,
Ĥ) [suitably encoded etc.] in both situations.)
To save possible problems here, it would be clearest to simply ban
global variables - they are not required, since all required input can
simply be passed to routines explicitly, and banning them eliminates one
possible source of objection to whatever you finally deliver.
Mike.
olcott
Sep 5, 2020, 11:51:24 PM9/5/20
to
UTM environment itself to keep track of heap allocations of memory.
Because user code can store a pointer to its heap allocated memory it
needs no global data at all.
I don't currently know of a way to distinguish between global data and
static local data or I could simply ban access to global data by user
code. It may say somewhere in the COFF file how to tell the difference.
>
>>
>> I don't have to show that H can correctly decide halting for every
>> possible encoding of the halting code. I only have to show that it is
>> not the H / H_hat template that prevents a correct halting decision.
>>
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>
olcott
Sep 5, 2020, 11:59:05 PM9/5/20
to
That is a good idea I think I will implement it as a compile time switch.
Richard Damon
Sep 6, 2020, 8:47:56 AM9/6/20
to
That makes the decision based on whether the machine M with input x will
halt or not.
>
> Linz Ĥ
> (q0)---->(qx)---->(HDC)---->(qy)---->(infinite_loop) or ((qn))
> based on same halting deciding code in (HDC).
Linz Ĥ(M, x)
> Linz Ĥ
> (q0)---->(qx)---->(HDC)---->(qy)---->(infinite_loop) or ((qn))
> based on same halting deciding code in (HDC).
That makes the decision based on whether the machine M with input x will
halt or not
Not sure where (qx) came from, and the or is placed a bit awkward too. I
might write it as:
(q0)---->(HDC)---->((qn)) or (qy)---->(infinite_loop)
>
> As long as the halt deciding code in HDC is the same in H and H_Hat and
> shows that its decision is correct then the Linz proof has been refuted.
> The halting code is the only unspecified detail of H or Ĥ.
>
> I make sure that the halting code is the same in H and Ĥ by having them
> both call the same function.
>
> I don't have to show that H can correctly decide halting for every
> possible encoding of the halting code. I only have to show that it is
> not the H / H_hat template that prevents a correct halting decision.
>
> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>
answer. That would require either showing an answer it could give that
meets the requirement (some sort of Non-Halting Halting??), or that
somehow the construction of Ĥ some how is an impossibility even if we
can make a H. I suppose the latter could be describe as it is not the H
/ H_Hat template that prevents a correct halting decision, but that
seems to be awkward wording, and seems more like trying to open up some
wiggle room for inserting a fallacious argument.
olcott
Sep 6, 2020, 12:43:14 PM9/6/20
to
start states.
>>
>> As long as the halt deciding code in HDC is the same in H and H_Hat and
>> shows that its decision is correct then the Linz proof has been refuted.
>> The halting code is the only unspecified detail of H or Ĥ.
>>
>> I make sure that the halting code is the same in H and Ĥ by having them
>> both call the same function.
>>
>> I don't have to show that H can correctly decide halting for every
>> possible encoding of the halting code. I only have to show that it is
>> not the H / H_hat template that prevents a correct halting decision.
>>
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>
>
> You need to break the paradox that Linz Ĥ(Ĥ, Ĥ) doesn't have a valid
> answer. That would require either showing an answer it could give that
> meets the requirement (some sort of Non-Halting Halting??), or that
> somehow the construction of Ĥ some how is an impossibility even if we
> can make a H. I suppose the latter could be describe as it is not the H
> / H_Hat template that prevents a correct halting decision, but that
> seems to be awkward wording, and seems more like trying to open up some
> wiggle room for inserting a fallacious argument.
>
http://www.liarparadox.org/Linz_Diagrams.pdf
André G. Isaak
Sep 6, 2020, 1:43:28 PM9/6/20
to
On 2020-09-06 10:42, olcott wrote:
> (qx) come from a correction to the Linz definition of H_hat having two
> start states.
You're going to have to clarify this. Where does Linz do this and how
> (qx) come from a correction to the Linz definition of H_hat having two
> start states.
does your qx correct this?
olcott
Sep 6, 2020, 2:04:40 PM9/6/20
to
On 9/6/2020 12:43 PM, André G. Isaak wrote:
> On 2020-09-06 10:42, olcott wrote:
>
>> (qx) come from a correction to the Linz definition of H_hat having two
>> start states.
>
> You're going to have to clarify this. Where does Linz do this and how
> does your qx correct this?
>
> André
>
Look at the Linz definition of H_Hat and notice that he has two (q0)
> On 2020-09-06 10:42, olcott wrote:
>
>> (qx) come from a correction to the Linz definition of H_hat having two
>> start states.
>
> You're going to have to clarify this. Where does Linz do this and how
> does your qx correct this?
>
> André
>
start states one after the other. I changed the name of the second one
to (qx).
I also wrote this succinct summary detailing the architecture of how my
x86 based UTM equivalent implements H and H_Hat.
olcott
Sep 6, 2020, 2:09:11 PM9/6/20
to
0 new messages