Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Counter-example to Rice's Theorem ?
80 views
Skip to first unread message
Peter Olcott
Feb 6, 2015, 7:57:17 AM2/6/15
to
The terminology and syntax shown below may have errors and/or not
consistently conform to standard conventions.
enum three_value_logic{FALSE, TRUE, ERROR}; // C++
{0,1,2} single digit on final tape of Turing Machine.
The halting property of (p,i) is true iff (if and only if) p is a
program that
halts on its input and false otherwise.
01 phd_3, p and i in Sigma*
02 <ThereExists> phd_3 in Partial_Halt_Deciders such that
03 <ForEach> p in Programs and <ForEach> i in Inputs
04 (phd_3(p,i) == halts(p,i)) <xor>
05 ((halts(p,i) != (phd_2(p,i) == FALSE)) <and>
06 (halts(p,i) != (phd_2(p,i) == TRUE)))
phd_3 correctly divides Program x Inputs into these two subsets:
1) On line 04 phd_3(p,i) would return either TRUE or FALSE corresponding
to halts(p,i).
This would correspond to correctly deciding the halting property for a
subset of
Program x Inputs.
2) On lines 05 and 06 phd_3(p,i) would return ERROR.
This would correspond to the impossibility of correctly deciding the
halting property
for a subset of Program x Inputs. // These lines have not yet been
reviewed by others
Automata and Computability Dexter Kozen (1997) Page 245
(Rice's Theorem) Every nontrivial property of the r.e. sets is undecidable.
The intent of the specification above is to divide up Program x Inputs
into the subset
of string pairs (p,i) where phd_3(p,i) can correctly decide the halting
property and
the subset of strings pairs (p,i) where correctly deciding halting is
impossible for phd_3(p,i).
The counter-example to Rice's Theorem arises because phd_3 correctly decides
whether or not it can correctly decide the halting property for every
element of
Program x Inputs.
consistently conform to standard conventions.
enum three_value_logic{FALSE, TRUE, ERROR}; // C++
{0,1,2} single digit on final tape of Turing Machine.
The halting property of (p,i) is true iff (if and only if) p is a
program that
halts on its input and false otherwise.
01 phd_3, p and i in Sigma*
02 <ThereExists> phd_3 in Partial_Halt_Deciders such that
03 <ForEach> p in Programs and <ForEach> i in Inputs
04 (phd_3(p,i) == halts(p,i)) <xor>
05 ((halts(p,i) != (phd_2(p,i) == FALSE)) <and>
06 (halts(p,i) != (phd_2(p,i) == TRUE)))
phd_3 correctly divides Program x Inputs into these two subsets:
1) On line 04 phd_3(p,i) would return either TRUE or FALSE corresponding
to halts(p,i).
This would correspond to correctly deciding the halting property for a
subset of
Program x Inputs.
2) On lines 05 and 06 phd_3(p,i) would return ERROR.
This would correspond to the impossibility of correctly deciding the
halting property
for a subset of Program x Inputs. // These lines have not yet been
reviewed by others
Automata and Computability Dexter Kozen (1997) Page 245
(Rice's Theorem) Every nontrivial property of the r.e. sets is undecidable.
The intent of the specification above is to divide up Program x Inputs
into the subset
of string pairs (p,i) where phd_3(p,i) can correctly decide the halting
property and
the subset of strings pairs (p,i) where correctly deciding halting is
impossible for phd_3(p,i).
The counter-example to Rice's Theorem arises because phd_3 correctly decides
whether or not it can correctly decide the halting property for every
element of
Program x Inputs.
Peter Olcott
Feb 6, 2015, 9:34:28 AM2/6/15
to
On 2/6/2015 8:01 AM, Ben Bacarisse wrote:
>> 06 (halts(p,i) != (phd_3(p,i) == TRUE)))
> phd_2 is unbound. Probably a typo for phd_3.
Yes
> Partial_Halt_Deciders is
> an undefined set.
I used the abbreviated notation that you specified.
Previously I always stated:
Partial_Halt_Deciders = Sigma*
Programs = Sigma*
Inputs = Sigma*
> You need to be clear what the notation m(p,i) means for
> machines m that don't halt on the input (p,i). (A common solution is to
> use an undefined value, often called "bottom" _|_ to denote the
> situation.)
phd_3 is specified (in the notes) to be a total Turing Machine because it
always returns exactly one of {FALSE, TRUE, ERROR}.
Perhaps there is some way to say this in the formal specification?
>
> <snip>
> formula.
>
I am still not clear on the exact difference between a quantified
formula and the
specification of elements of a set. It seems to me that I have specified
at least
one element of Sigma*.
It would seem that this element must also be either the encoding of a
machine
or the encoding of a software function because a random string could not
correctly divide the set of all possible finite string pairs into the
subset that it
correctly decides and the subset where correctly deciding is impossible
for it.
Because of this it would seem that phd_3 would specify at least one literal
string that is the encoding of a Turing Machine or a software function.
> Peter Olcott <OCR4Screen> writes:
>
>> The terminology and syntax shown below may have errors and/or not
>> consistently conform to standard conventions.
>>
>> enum three_value_logic{FALSE, TRUE, ERROR}; // C++
>> {0,1,2} single digit on final tape of Turing Machine.
>>
>> The halting property of (p,i) is true iff (if and only if) p is a
>> program that
>> halts on its input and false otherwise.
>>
>> 01 phd_3, p and i in Sigma*
>> 02 <ThereExists> phd_3 in Partial_Halt_Deciders such that
>> 03 <ForEach> p in Programs and <ForEach> i in Inputs
>> 04 (phd_3(p,i) == halts(p,i)) <xor>
>> 05 ((halts(p,i) != (phd_3(p,i) == FALSE)) <and>
>
>> The terminology and syntax shown below may have errors and/or not
>> consistently conform to standard conventions.
>>
>> enum three_value_logic{FALSE, TRUE, ERROR}; // C++
>> {0,1,2} single digit on final tape of Turing Machine.
>>
>> The halting property of (p,i) is true iff (if and only if) p is a
>> program that
>> halts on its input and false otherwise.
>>
>> 01 phd_3, p and i in Sigma*
>> 02 <ThereExists> phd_3 in Partial_Halt_Deciders such that
>> 03 <ForEach> p in Programs and <ForEach> i in Inputs
>> 04 (phd_3(p,i) == halts(p,i)) <xor>
>> 06 (halts(p,i) != (phd_3(p,i) == TRUE)))
> phd_2 is unbound. Probably a typo for phd_3.
Yes
> Partial_Halt_Deciders is
> an undefined set.
I used the abbreviated notation that you specified.
Previously I always stated:
Partial_Halt_Deciders = Sigma*
Programs = Sigma*
Inputs = Sigma*
> You need to be clear what the notation m(p,i) means for
> machines m that don't halt on the input (p,i). (A common solution is to
> use an undefined value, often called "bottom" _|_ to denote the
> situation.)
phd_3 is specified (in the notes) to be a total Turing Machine because it
always returns exactly one of {FALSE, TRUE, ERROR}.
Perhaps there is some way to say this in the formal specification?
>
> <snip>
>> The counter-example to Rice's Theorem arises because phd_3 correctly decides
>> whether or not it can correctly decide the halting property for every
>> element of
>> Program x Inputs.
> phd_3 is not a machine or function. It is the name used in a quantified
>> whether or not it can correctly decide the halting property for every
>> element of
>> Program x Inputs.
> formula.
>
I am still not clear on the exact difference between a quantified
formula and the
specification of elements of a set. It seems to me that I have specified
at least
one element of Sigma*.
It would seem that this element must also be either the encoding of a
machine
or the encoding of a software function because a random string could not
correctly divide the set of all possible finite string pairs into the
subset that it
correctly decides and the subset where correctly deciding is impossible
for it.
Because of this it would seem that phd_3 would specify at least one literal
string that is the encoding of a Turing Machine or a software function.
Peter Olcott
Feb 6, 2015, 9:41:18 AM2/6/15
to
On 2/6/2015 8:04 AM, Ben Bacarisse wrote:
> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>> an undefined set. You need to be clear what the notation m(p,i) means for
>
I do not know what you mean about the forall.
Partial_Halt_Deciders, Programs, Inputs = Sigma*
provide a counter-example showing that phd_3 does not exist?
> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>
>> Peter Olcott <OCR4Screen> writes:
>>
>>> The terminology and syntax shown below may have errors and/or not
>>> consistently conform to standard conventions.
>>>
>>> enum three_value_logic{FALSE, TRUE, ERROR}; // C++
>>> {0,1,2} single digit on final tape of Turing Machine.
>>>
>>> The halting property of (p,i) is true iff (if and only if) p is a
>>> program that
>>> halts on its input and false otherwise.
>>>
>>> 01 phd_3, p and i in Sigma*
>>> 02 <ThereExists> phd_3 in Partial_Halt_Deciders such that
>>> 03 <ForEach> p in Programs and <ForEach> i in Inputs
>>> 04 (phd_3(p,i) == halts(p,i)) <xor>
>>> 05 ((halts(p,i) != (phd_2(p,i) == FALSE)) <and>
>>> 06 (halts(p,i) != (phd_2(p,i) == TRUE)))
>> phd_2 is unbound. Probably a typo for phd_3. Partial_Halt_Deciders is
>> Peter Olcott <OCR4Screen> writes:
>>
>>> The terminology and syntax shown below may have errors and/or not
>>> consistently conform to standard conventions.
>>>
>>> enum three_value_logic{FALSE, TRUE, ERROR}; // C++
>>> {0,1,2} single digit on final tape of Turing Machine.
>>>
>>> The halting property of (p,i) is true iff (if and only if) p is a
>>> program that
>>> halts on its input and false otherwise.
>>>
>>> 01 phd_3, p and i in Sigma*
>>> 02 <ThereExists> phd_3 in Partial_Halt_Deciders such that
>>> 03 <ForEach> p in Programs and <ForEach> i in Inputs
>>> 04 (phd_3(p,i) == halts(p,i)) <xor>
>>> 05 ((halts(p,i) != (phd_2(p,i) == FALSE)) <and>
>>> 06 (halts(p,i) != (phd_2(p,i) == TRUE)))
>> an undefined set. You need to be clear what the notation m(p,i) means for
>> machines m that don't halt on the input (p,i). (A common solution is to
>> use an undefined value, often called "bottom" _|_ to denote the
>> situation.)
>>
>> <snip>
>> use an undefined value, often called "bottom" _|_ to denote the
>> situation.)
>>
>>> The counter-example to Rice's Theorem arises because phd_3 correctly decides
>>> whether or not it can correctly decide the halting property for every
>>> element of
>>> Program x Inputs.
>>> whether or not it can correctly decide the halting property for every
>>> element of
>>> Program x Inputs.
>> phd_3 is not a machine or function. It is the name used in a quantified
>> formula.
> That's wrong. It is not in a forall. You need to prove that it exists.
>> formula.
>
I do not know what you mean about the forall.
Partial_Halt_Deciders, Programs, Inputs = Sigma*
<ThereExists> phd_3 in Partial_Halt_Deciders such that
<ForEach> p in Programs and <ForEach> i in Inputs
(phd_3(p,i) == halts(p,i)) <xor>
((halts(p,i) != (phd_3(p,i) == FALSE)) <and>
(halts(p,i) != (phd_3(p,i) == TRUE)))
Maybe now at least I have a clear basis for someone else to
provide a counter-example showing that phd_3 does not exist?
Martin Shobe
Feb 6, 2015, 10:44:00 AM2/6/15
to
exist. Good luck with that. Especially as we can construct, for each
phd_3, a machine, c, in the following way.
C(p, i)
{
if (phd_3(p,i) == false)
{
return;
}
while (1);
}
Now, halts(C, i) is true if and only if phd_3(C, i) is false.
Therefore, if phd_3(C, i) returns TRUE halts(C, i) is false. Therefore,
(phd_3(p,i) == halts(p,i)) <xor> ((halts(p,i) != (phd_3(p,i) ==
FALSE)) <and> (halts(p,i) != (phd_3(p,i) == TRUE)))
(TRUE == FALSE) <xor> ((FALSE != (TRUE == FALSE)) <and> (FALSE !=
FALSE)) <and> (halts(p,i) != (phd_3(p,i) == TRUE)))
(TRUE == TRUE)))
FALSE <xor> ((FALSE != FALSE) <and> (FALSE != TRUE))
FALSE <xor> (FALSE <and> TRUE)
FALSE <xor> FALSE
FALSE
So, if phd_3 meets the requirements, phd_3 does not return TRUE.
If phd_3(C, i) returns FALSE, halts(C, i) is true. Therefore,
(phd_3(p,i) == halts(p,i)) <xor> ((halts(p,i) != (phd_3(p,i) ==
FALSE)) <and> (halts(p,i) != (phd_3(p,i) == TRUE)))
(FALSE == TRUE) <xor> ((TRUE != (FALSE == FALSE)) <and> (TRUE !=
FALSE)) <and> (halts(p,i) != (phd_3(p,i) == TRUE)))
(FALSE == TRUE)))
FALSE <xor> ((TRUE != TRUE) <and> (TRUE != FALSE))
FALSE <xor> (FALSE <and> TRUE)
FALSE <xor> FALSE
FALSE
So, if phd_3 meets the requirements, phd_3 does not return FALSE.
If phd_3(C, i) returns anything else (we'll call it X), halts(C, i) is
false. Therefore,
(phd_3(p,i) == halts(p,i)) <xor> ((halts(p,i) != (phd_3(p,i) ==
FALSE)) <and> (halts(p,i) != (phd_3(p,i) == TRUE)))
(X == FALSE) <xor> ((FALSE != (X == FALSE)) <and> (FALSE != (X ==
FALSE)) <and> (halts(p,i) != (phd_3(p,i) == TRUE)))
TRUE)))
FALSE <xor> ((FALSE != FALSE) <and> (FALSE != FALSE))
FALSE <xor> (FALSE <and> FALSE)
FALSE <xor> FALSE
FALSE
So, if phd_3 meets the requirements, phd_3 does not return anything
else.
If phd_3 doesn't return anything, it doesn't meet the requirements.
Therefore, phd_3 doesn't meet the requirements. Since phd_3 was an
arbitrary machine, There are no machines that meet the requirements.
Martin Shobe
Peter Olcott
Feb 6, 2015, 1:15:19 PM2/6/15
to
The new matter has to be specified as pseudo code because I don't currently
know how to say it using predicate logic.
Partial_Halt_Deciders, Programs, Inputs = Sigma*
<ThereExists> phd_3 in Partial_Halt_Deciders such that
<ForEach> p in Programs and <ForEach> i in Inputs
(phd_3(p,i) == halts(p,i)) <xor>
phd_3(p,i)_returns_TRUE))
Peter Olcott
Feb 6, 2015, 2:11:00 PM2/6/15
to
On 2/6/2015 9:43 AM, Martin Shobe wrote:
Partial_Halt_Deciders, Programs, Inputs = Sigma*
<ThereExists> phd_3 in Partial_Halt_Deciders such that
<ForEach> p in Programs and <ForEach> i in Inputs
(phd_3(p,i) == halts(p,i)) <xor>
phd_3(p,i)_returns_TRUE))
C(p, i)
{
if (phd_3(p,i) == false)
return;
while (1);
}
(phd_3(C,i)_returns_FALSE <or>
phd_3(C,i)_returns_TRUE)))
return ERROR;
It is still pseudo-code rather then predicate logic, yet that is the best
that I can do currently.
Peter Olcott
Feb 6, 2015, 4:20:47 PM2/6/15
to
On 2/6/2015 1:03 PM, Martin Shobe wrote:
> Go learn some computer science. That pseudo-code can't be implemented
> by any TM (or equivalent computational device) as it requires that the
> TM evaluate halts(p,i), which isn't computable.
>
> Furthermore, you'll need to give the semantics of <ThereExists> and
> <ForEach> in the pseudo-code.
>
> Martin Shobe
>
I think that it is a subtle error to say that no TM can evaluate
halts(p,i) the actual
truth is that no TM can consistently return a value that corresponds to
halts(p,i).
My whole point crucially depends upon this single quite subtle distinction.
It seems to me that a TM could (as I have specified above) either report
a value
corresponding to halts(p,i) or report that it is not possible for it to
report a value
corresponding to halts(p,i) for every (p,i) in Programs x Inputs.
The above may now be sufficiently precise such that a counter-example
proving
me wrong might be provided iff (if and only if) I am actually incorrect.
I will keep
trying to find a pure predicate logic way of stating this new material.
I am so
impressed as to be enamored by the precision of predicate logic in
expressing
ideas in clear indisputable ways.
I am using predicate logic where-so-ever I can within the limitations of
my current
knowledge, thus the PL meaning of the quantifier symbols continues to
hold for their
ASCII text equivalents.
> by any TM (or equivalent computational device) as it requires that the
> TM evaluate halts(p,i), which isn't computable.
>
> Furthermore, you'll need to give the semantics of <ThereExists> and
> <ForEach> in the pseudo-code.
>
> Martin Shobe
>
I think that it is a subtle error to say that no TM can evaluate
halts(p,i) the actual
truth is that no TM can consistently return a value that corresponds to
halts(p,i).
My whole point crucially depends upon this single quite subtle distinction.
It seems to me that a TM could (as I have specified above) either report
a value
corresponding to halts(p,i) or report that it is not possible for it to
report a value
corresponding to halts(p,i) for every (p,i) in Programs x Inputs.
The above may now be sufficiently precise such that a counter-example
proving
me wrong might be provided iff (if and only if) I am actually incorrect.
I will keep
trying to find a pure predicate logic way of stating this new material.
I am so
impressed as to be enamored by the precision of predicate logic in
expressing
ideas in clear indisputable ways.
I am using predicate logic where-so-ever I can within the limitations of
my current
knowledge, thus the PL meaning of the quantifier symbols continues to
hold for their
ASCII text equivalents.
Peter Olcott
Feb 6, 2015, 6:15:56 PM2/6/15
to
On 2/6/2015 3:39 PM, Kaz Kylheku wrote:
> computer science that applies to programming language semantics. To evaluate
> means to reduce an expression to a value. Since halts(p, i) is a mathematical
> function, that is not applicable. What a procedure (or TM) does is to calculate
> the value of of a function for some argument values, such halts(p, i), or
> cos(0.3) or whatever.
Not<ThereExists> phd in Partial_Halt_Deciders such that
phd(p,i) == halts(p,i) for all (p,i) in Programs x Inputs
// No specific phd decides halting correctly for every input.
It might be possible to iterate through phd in Partial_Halt_Deciders
such that phd(p,i) == halts(p,i) <ForEach> (p,i) in Programs x Inputs
// It may be possible to search for and find a phd that correctly decides
// any specific element of Programs x Inputs
// This would a a whole lot like finding a solution to the Halting Problem
*Halting Problem Solution* ???
Alternatively it may be possible to automatically dynamically construct a
halting decider for any possible specific static input string.
> If you simply mean "consistently with halts(p, i)"
> then it is redundant. Any discrepancy makes the calculation incorrect. If the
> calculation doesn't terminate for any <p, i>, with the correct value, then the
> calculation is said not to be "total". At best, the function can be correct
> for some defined subset of the p X i space; in which case it is "partial"
> rather than "total".
>
> If you mean "consistently from one invocation to another, given the same
> arguments", then that is a given; lack of such consistency means that the
> calculation isn't computing a mathematical function. It is depending
> on some hidden environmental inputs, or persistent state.
>
> There is no need for you or anyone else to invent any new terminology, in
> any case.
> function is concerned.
>
> It could be a correct value of some other function: one which has
> a three-valued range.
>
> But it is definitely not a correct halting decider.
I am only seeking to specify a halting decider decider, not a halting
decider.
>
> It also cannot be a total decider for the three-valued function
> that you would like. That is easy to show. No three-valued decider can
> correctly calculate the third error value either.
>
> Your only claim in support of the contrary view is that some magic
> exception exists in Rice's Theorem, which is the fallacy of special pleading.
Not at all. I propose that no valid counter example can possibly be found
that can prove that I am incorrect.
> http://en.wikipedia.org/wiki/Special_pleading
>
> "Special pleading is a form of fallacious argument that involves an attempt to
> cite something as an exception to a generally accepted rule, principle, etc.
> without justifying the exception."
>
> E.g. "This is an exception to Rice's Theorem, because I *feel* that it must
> be so."
> On 2015-02-06, Peter Olcott <OCR4Screen> wrote:
>> I think that it is a subtle error to say that no TM can evaluate
>> halts(p,i) the actual
> That is more than a subtle error; that is an error of abusing the vocabulary of
>> I think that it is a subtle error to say that no TM can evaluate
>> halts(p,i) the actual
> computer science that applies to programming language semantics. To evaluate
> means to reduce an expression to a value. Since halts(p, i) is a mathematical
> function, that is not applicable. What a procedure (or TM) does is to calculate
> the value of of a function for some argument values, such halts(p, i), or
> cos(0.3) or whatever.
>
>> truth is that no TM can consistently return a value that corresponds to
>> halts(p,i).
> "Consistently" is vague.
>> truth is that no TM can consistently return a value that corresponds to
>> halts(p,i).
Not<ThereExists> phd in Partial_Halt_Deciders such that
phd(p,i) == halts(p,i) for all (p,i) in Programs x Inputs
// No specific phd decides halting correctly for every input.
It might be possible to iterate through phd in Partial_Halt_Deciders
such that phd(p,i) == halts(p,i) <ForEach> (p,i) in Programs x Inputs
// It may be possible to search for and find a phd that correctly decides
// any specific element of Programs x Inputs
// This would a a whole lot like finding a solution to the Halting Problem
*Halting Problem Solution* ???
Alternatively it may be possible to automatically dynamically construct a
halting decider for any possible specific static input string.
> If you simply mean "consistently with halts(p, i)"
> then it is redundant. Any discrepancy makes the calculation incorrect. If the
> calculation doesn't terminate for any <p, i>, with the correct value, then the
> calculation is said not to be "total". At best, the function can be correct
> for some defined subset of the p X i space; in which case it is "partial"
> rather than "total".
>
> If you mean "consistently from one invocation to another, given the same
> arguments", then that is a given; lack of such consistency means that the
> calculation isn't computing a mathematical function. It is depending
> on some hidden environmental inputs, or persistent state.
>
> There is no need for you or anyone else to invent any new terminology, in
> any case.
>
>> My whole point crucially depends upon this single quite subtle distinction.
>>
>> It seems to me that a TM could (as I have specified above) either report
>> a value
>> corresponding to halts(p,i) or report that it is not possible for it to
>> report a value
>> corresponding to halts(p,i) for every (p,i) in Programs x Inputs.
> Such a report is just an incorrect value, as far as the halts(p, i)
>> My whole point crucially depends upon this single quite subtle distinction.
>>
>> It seems to me that a TM could (as I have specified above) either report
>> a value
>> corresponding to halts(p,i) or report that it is not possible for it to
>> report a value
>> corresponding to halts(p,i) for every (p,i) in Programs x Inputs.
> function is concerned.
>
> It could be a correct value of some other function: one which has
> a three-valued range.
>
> But it is definitely not a correct halting decider.
I am only seeking to specify a halting decider decider, not a halting
decider.
>
> It also cannot be a total decider for the three-valued function
> that you would like. That is easy to show. No three-valued decider can
> correctly calculate the third error value either.
>
> Your only claim in support of the contrary view is that some magic
> exception exists in Rice's Theorem, which is the fallacy of special pleading.
Not at all. I propose that no valid counter example can possibly be found
that can prove that I am incorrect.
> http://en.wikipedia.org/wiki/Special_pleading
>
> "Special pleading is a form of fallacious argument that involves an attempt to
> cite something as an exception to a generally accepted rule, principle, etc.
> without justifying the exception."
>
> E.g. "This is an exception to Rice's Theorem, because I *feel* that it must
> be so."
X.Y. Newberry
Feb 6, 2015, 9:04:46 PM2/6/15
to
subroutine and partition the space into positively halting, positively
not halting, and self-referential. This was proposed by Herc on this
board and it may be the right idea. The self-referential subset is
undecidable.
--
X.Y. Newberry
If Jack says ‘What I am saying at this very moment is not true’, we can
successfully and truly assert that he did not utter a truth: ‘What Jack
said is not true’. But it is hardly conceivable that Jack’s utterance is
true by virtue of its success in attributing non-truth to itself.
Haim Gaifman
Peter Olcott
Feb 6, 2015, 9:12:16 PM2/6/15
to
He asked about equivalent programs. It then occurred to me
that if we simply assign 123 to a dummy variable at the
beginning of the program we could have an equivalent program
that is not the same program.
I am not going to bother with categorically examining every possible
case where
ERROR might be returned other than the single common factor that:
(halts(p,i) != (phd_2(p,i) _returns_FALSE)) <and>
(halts(p,i) != (phd_2(p,i)_returns_TRUE))
Christian Gollwitzer
Feb 7, 2015, 5:04:04 AM2/7/15
to
Am 06.02.15 um 22:20 schrieb Peter Olcott:
could just run the given program for, say, 1000 instructions. If it
halts during that time, return TRUE. If not, return ERROR.
Christian
> I think that it is a subtle error to say that no TM can evaluate
> halts(p,i) the actual truth is that no TM can consistently return a
> value that corresponds to halts(p,i). My whole point crucially depends upon this single quite subtle distinction.
>
> It seems to me that a TM could (as I have specified above) either
> report a value corresponding to halts(p,i) or report that it is not
> possible for it to report a value corresponding to halts(p,i) for
> every (p,i) in Programs x Inputs.
I think this is easy to prove, unless I misunderstood that sentence. You
> halts(p,i) the actual truth is that no TM can consistently return a
> value that corresponds to halts(p,i). My whole point crucially depends upon this single quite subtle distinction.
>
> It seems to me that a TM could (as I have specified above) either
> report a value corresponding to halts(p,i) or report that it is not
> possible for it to report a value corresponding to halts(p,i) for
> every (p,i) in Programs x Inputs.
could just run the given program for, say, 1000 instructions. If it
halts during that time, return TRUE. If not, return ERROR.
Christian
Peter Olcott
Feb 7, 2015, 12:57:37 PM2/7/15
to
way of saying *exactly* what I mean.
There exists a TM, m, such that
for every (p, i) in Sigma* x Sigma*
m(p, i) halts with
m(p, i) in {TRUE, FALSE, ERROR} <and>
(halts(p, i) == m(p, i) <xor>
(halts(p, i) != (m(p, i) = FALSE) <and>
halts(p, i) != (m(p, i) = TRUE)))
X.Y. Newberry
Feb 9, 2015, 11:46:10 PM2/9/15
to
Peter Olcott
Feb 10, 2015, 7:44:34 AM2/10/15
to
It seems to be that both self-referentiality and any of its equivalents are
*all* being decided. Also it is not just self-referentiality, yet *only*
those
cases where self-referentiality prevents halting from being decided.
Pathological Self Reference (PSR) is the case where actual self-reference
to a TM m by its input data causes neither TRUE nor FALSE to be a correct
return value corresponding to m(p,i).
The equivalent of self-reference would the the case where a the input to
TM m (p,i) includes another TM m2 that is equivalent to m in that for this
specific instance of m and m2, and this specific instance of (p,i) in
Programs x
Inputs m2 would return the same value that m would return.
A TM m2 that is identical to m has the effect of a TM that is equivalent
to m
and not the same effect as m itself, when m itself is directly included
in (p,i).
When m is directly included in (p,i) then the three return values of m
actually
change the literal string pair of (p,i). When m2 is merely identical to
m, then
the three return values of m do not change the literal string pair (p,i).
To refer back to my original terminology, when-so-ever any Turing Machine m
is presented with any essentially (yes/no) question that lacks a correct
answer
from the set of (yes/no), such that neither yes nor no returned by m forms
a correct answer to this (yes/no) question, m simply decides that this
question
when posed to itself is incorrect and thus returns NEITHER.
The above generally applies to *any* undecidable property of (p,i) and
is thus
not limited to merely the halting property of (p,i). Therefore m can
*always*
decide the decidability of any nontrivial property of the r.e. sets, thereby
forming a counter-example disproving Rice's Theorem.
Automata and Computability, Dexter Kozen (1997) page 245:
(Rice's Theorem) Every nontrivial property of the r.e. sets is undecidable.
//
// m is a string encoding of a Turing Machine
// m(p,i)(TRUE) means: m(p,i) leaves a single 1 digit on the tape
// m(p,i)(FALSE) means: m(p,i) leaves a single 0 digit on the tape
// m(p,i)(ERROR) means: m(p,i) leaves a single 2 digit on the tape
//
01 There exists a TM, m, such that
02 for every (p, i) in Sigma* x Sigma*
03 m(p, i) halts with
04 m(p, i) in {TRUE, FALSE, ERROR} <and>
05 (halts(p, i) == m(p, i)(TRUE) <xor>
06 halts(p, i) == m(p, i)(FALSE) <xor>
07 (halts(p,i) != m(p,i)(TRUE) <and> halts(p,i) != m(p,i)(FALSE))
Line 05 specifies the subset of Sigma* x Sigma* where returning
TRUE would be correct.
Line 06 specifies the subset of Sigma* x Sigma* where returning
FALSE would be correct.
Line 07 specifies the subset of Sigma* x Sigma* where returning TRUE
or returning FALSE would *both* be incorrect, thus it returns ERROR.
0 new messages