XPost: comp.theory, sci.logic, sci.math   
   From: mikko.levanto@iki.fi   
      
   On 13/01/2026 20:23, Tristan Wibberley wrote:   
   > On 13/01/2026 14:34, olcott wrote:   
   >> On 1/13/2026 8:23 AM, Tristan Wibberley wrote:   
   >>> On 13/01/2026 09:11, Mikko wrote:   
   >>>> An oracle machine may be   
   >>>> able to determine the haltinf of all Turing machines but not of all   
   >>>> oracle machines with the same oracle (or oracles) so it is not   
   >>>> universal.   
   >>>   
   >>> What's the formal definition of "an oracle machine" ?   
   >>>   
   >>> I would have thought an oracle always halts because it's an oracle it   
   >>> answers every question that has an answer with either "HasAnswer answer"   
   >>> or "HasNoAnswer".   
   >>>   
   >>   
   >> It seems outside of computer science and into fantasy.   
   >> https://en.wikipedia.org/wiki/Oracle_machine   
   >>   
   >   
   > Perhaps a halting oracle is real computer science, if it's own actions   
   > are nondeterministic (ie, use bits of entropy from the environment via   
   > /dev/random to guide its search through confluent paths) then it could   
   > always find whether a deterministic program halts because no   
   > deterministic program has the oracle as a subprogram.   
      
   A non-deterministic machine can be modelled as a deterministic machine   
   with an extra input. Questions about a non-deterministic machine can   
   then be interpreted as questions where that extra input is quatified   
   (usually existentially but possibly universally, depending on how the   
   question is presented).   
      
   > Then we have a new but different problem of making sure no two oracles   
   > receive the same sequence of entropy bits so an oracle can report on a   
   > program that contains it.   
      
   For a non-deterministic machine there are three possibilities: it may   
   halt always, sometimes, or never. THere is no oracle that can find the   
   right answer about every meachne that contains the same oracle.   
      
   --   
   Mikko   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)