On 7/17/2021 10:12 AM, Alan Mackenzie wrote:
> Mr Flibble <flibble@reddwarf.jmc> wrote:
>> On Sat, 17 Jul 2021 14:45:27 -0000 (UTC)
>> Alan Mackenzie <acm@muc.de> wrote:
>
>>> Mr Flibble <flibble@reddwarf.jmc> wrote:
>>>> On Sat, 17 Jul 2021 14:34:53 -0000 (UTC)
>>>> Alan Mackenzie <acm@muc.de> wrote:
>
>>>>> Mr Flibble <flibble@reddwarf.jmc> wrote:
>>>>>> On Sat, 17 Jul 2021 14:20:42 -0000 (UTC)
>>>>>> Alan Mackenzie <acm@muc.de> wrote:
>
>>>>>>> Mr Flibble <flibble@reddwarf.jmc> wrote:
>>>>>>>> On Sat, 17 Jul 2021 13:59:02 -0000 (UTC)
>>>>>>>> Alan Mackenzie <acm@muc.de> wrote:
>
>>>>>>>>> Mr Flibble <flibble@reddwarf.jmc> wrote:
>>>>>>>>>> On Sat, 17 Jul 2021 13:22:56 -0000 (UTC)
>>>>>>>>>> Alan Mackenzie <acm@muc.de> wrote:
>>>>>>>>>>> Not really - you don't have a universal halting decider
>>>>>>>>>>> here by design. And even if you did, the signature
>>>>>>>>>>> wouldn't do anything to prevent the existence of the
>>>>>>>>>>> programs which have an "invalid relationship" with D.
>
>
>>>>>>>>>> The point is that this "invalid relationship" is
>>>>>>>>>> DETECTABLE by the black box decider.
>
>>>>>>>>> I think, but I'm not sure, that such relationships cannot be
>>>>>>>>> detected, that it's another one of these limitation theorems.
>>>>>>>>> Ben could probably say more on this.
>
>>>>>>>>>> This "invalid relationship" only exists for programs which
>>>>>>>>>> are deliberately designed to defeat the decider ....
>
>
>>>>>>>>> Not at all. There will be random programs, not deliberately
>>>>>>>>> designed, which will also have such a relationship with the
>>>>>>>>> purported decider.
>
>>>>>>>>>> .... which are uninteresting cases because presumably we
>>>>>>>>>> are using a decider to decide legitimate programs that
>>>>>>>>>> have serve some useful purpose beyond the HP itself.
>
>
>>>>>>>>> Then you're not talking about the standard halting problem.
>>>>>>>>> That shows the impossibility of a decider which can decide
>>>>>>>>> ANY program. If you limit the scope of the programs handled,
>>>>>>>>> then you might well construct a practically useful partial
>>>>>>>>> decider. Difficult, but possible. There are probably
>>>>>>>>> theorems about the sort of things that are possible here,
>>>>>>>>> but I don't know them.
>
>
>>>>>>>>> None of this has any relevance for the theoremhood of the
>>>>>>>>> halting problem result itself.
>
>>>>>>>> Disagree: having a third result for invalid pathological
>>>>>>>> programs whilst novel is still a result, i.e. a decision
>>>>>>>> reached in finite time.
>
>>>>>>> Let me stress again that there is nothing invalid or
>>>>>>> pathological about these programs, and they can run and halt or
>>>>>>> not halt like any other program. It is only in their
>>>>>>> relationship with H where they are special, in that H is unable
>>>>>>> to determine their halting status correctly.
>
>>>>>>> That's assuming it's possible for H to single out such
>>>>>>> programs. I don't know if this is possible in the general
>>>>>>> case, but I suspect it's not. Again, Ben or Richard might know
>>>>>>> more about this.
>
>>>>>>> But all this is moving away from the halting problem.
>
>>>>>> Disagree: as the decider is a black box if it can always detect
>>>>>> when it is being invoked, either directly by the trusted operator
>>>>>> or indirectly by P which does not have the trusted operator's
>>>>>> private key in order to digitally sign P and I that is passed to
>>>>>> the decider.
>
>>>>> P might contain a copy of D's algorithm (with or without the key
>>>>> stuff), and indeed P might contain a copy of the private key. Such
>>>>> programs _exist_, whether or not we could as humans create them.
>>>>> As I say, I don't think it's possible for D to detect an algorithm
>>>>> which does the same as D.
>
>>>>> But in any case, D is not behaving as a universal halting
>>>>> detector, in that it doesn't return halts/doesn't halt for all
>>>>> input programs.
>
>>>> I suggest you read up on what constitutes a black box: if the black
>>>> box's algorithm has been copied then it is no longer a black box.
>
>>> OK, then black boxes are, at this level of theory, not possible
>>> objects. Note I didn't say "has been copied", but "contains a copy",
>>> i.e. just randomly happens to match up. Such randomly matching
>>> programs exist.
>
>> That assumes that the black box decider cannot detect when P and I are
>> being passed to something equivalent to the black box;
>
> Again, I'm beyond the limits of my knowledge, but I think it's a theorem
> that it is not possible to determine in general that two turing machines
> have the same functionality.

In computability theory, Rice's theorem states that all non-trivial,
semantic properties of programs are undecidable. A semantic property is
one about the program's behavior (for instance, does the program
terminate for all inputs), unlike a syntactic property (for instance,
does the program contain an if-then-else statement).

https://en.wikipedia.org/wiki/Rice%27s_theorem

> In that case, the black box decider could
> not recognise something which happens to be a copy of its essentials.
>
>> you know what they say about assumptions, right?
>
> Indeed. You've been doing a fair amount of it yourself in constructing
> this black box idea. ;-)
>
>> The black box decider could certainly detect if P and I are being
>> passed to something opaque and treat that as pathological behavior.
>
> It's not certain at all. See above.
>
>> /Flibble
>

--
Copyright 2021 Pete Olcott

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