XPost: comp.theory, alt.messianic   
   From: user7160@newsgrouper.org.invalid   
      
   my proposal starts with the reminder that *no* machine computes a unique   
   function. for every function that is computed, there is a whole   
   (infinite) class of machines that are functionally equivalent (same   
   input -> same output behavior).   
      
   we should then consider a working thesis: no paradoxical machine is the   
   simplest of their class of functionally equivalent machines.   
      
   why? the paradox structures do not actually contribute to the output   
   (since deciders themselves do not create output for the “calling”   
   machine), they are just sort of junk computation that selects a   
   particular execution branch (or blocks entirely), a result which can   
   exist without that paradox fluff being involved.   
      
   consider the basic paradox form:   
      
      deciderP(input) - decides if input has property P or !P   
      machineP()      - machine that has property P   
      machine!P()     - machine that has property !P   
      
      // undecidable by deciderP for property P   
      undP = () -> {   
        if ( deciderP(undP) == TRUE )   
          machine!P()   
        else   
          machineP()   
      }   
      
   huh, i guess i kinda get why this wasn’t really spotted before. as far   
   as i can tell, classical computing theory normally recognizes three   
   kinds of classifiers:   
      
      
      classical decider:   
        TRUE iff input has P   
        FALSE iff input has !P (always DECIDABLE)   
        impossible interface   
      
      classical recognizer:   
        TRUE iff input has P (always DECIDABLE)   
        FALSE iff input has !P (block if UNDECIDABLE)   
      
      partial decider:   
        TRUE iff input has P   
        FALSE iff input has !P   
        (block if either UNDECIDABLE)   
      
   ... so the paradoxes (involving either a classical recognizer or partial   
   decider) always result in a blocking, non-returning program making this   
   thesis still valid, but less interesting/compelling.   
      
   i have instead been working on the logical interface for alternative   
   classifiers. one example are the context-aware classifiers i’ve been   
   previously posting quite a bit on, but let’s consider a less general   
   classifier that might exist on TMs alone, what i’m calling a partial   
   recognizer:   
      
      partial recognizer   
        TRUE iff input has P AND is DECIDABLE   
        FALSE iff input has !P OR is UNDECIDABLE   
      
   in this case if we consider undP() from above ... deciderP(undP) would   
   return FALSE because undP is UNDECIDABLE by deciderP(). but that doesn’t   
   mean the program isn’t runnable. it certainly is, and when u do run it,   
   it will have the functional behavior of machineP(). which may even halt,   
   mind you,   
      
   ...there’s this weird notion floating around that because halting   
   machines are certainly enumerable, therefore it’s not possible to create   
   an undecidable halting machine. but that’s not actually true, paradoxes   
   are constructed in regards to *specific* interfaces (classes of   
   functionally equivalent machines), not general ability. therefore,   
   despite the fact we can enumerate out all halting machines, it’s still   
   possible to construct a halting machine that is also a paradox in   
   respect to some property classifier like deciderP(). anyways...   
      
   atm i’d like to point out that undP(), despite being undecidable by   
   deciderP() in regards to property P, is functionally equivalent to   
   machineP() when run and therefore must have property P. and i hope you   
   can now start to see how the paradox construction prevents the machine   
   from being the simplest in its class of functionally equivalent machine.   
   ultimately such a binary paradox is formed by having two branches which   
   opposing semantic properties, selected specifically by the opposing   
   return value of a classifier for to a particular property. the paradox   
   machine will either run one of those branches (making it functionally   
   equivalent to the branch that is run) or block on the classifier call   
   (making it functionally equivalent to a basic infinite loop). therefore   
   the paradox *cannot* be the simplest machine in its class of   
   functionally equivalent machines.   
      
   why does this matter? because therefore there exists not only a turing   
   complete subset of machines that has no paradoxical machines, but a   
   minimal turing complete subset containing only the least complex form of   
   any given function computation, that has no machine which might cause   
   *any* classifier to be unable to classify it.   
      
   but can we decide on such a minimal turing complete subset? the gut   
   reaction from 99.99% of you will be a hard no, also undecidable!! 😤 and   
   continue to get all butthurt over the mere suggestion that turing was   
   wrong about literally anything ever. but look, that undecidability is   
   *just another form* of the same tired old semantic paradox that has been   
   plaguing computing since turing wrote the first paper on computable   
   numbers, and therefore *it also need not be included within a minimal   
   turing complete subset.*   
      
   we can form this subset by utilizing a partial   
   non-functional-equivalence recognizer that focuses on computing when two   
   machines do not compute the same function. such a classifier will have   
   the interface:   
      
      not_func_eq = (machineA, machineB) -> {   
        TRUE if machineA does NOT compute the same function as machineB   
          AND such decision is DECIDABLE,   
        FALSE if machine A does compute the same function as machineB   
          OR such decision is UNDECIDABLE,   
      }   
      
      
   as we then iterate across the full enumeration of turing machines, we   
   can use not_func_eq() as a filter to create a minimal turing complete   
   subset:   
      
      () -> {   
        min_tc_subset = []   
        for (n = 0; true; n++) {   
          if (   
            // test only runnable machines   
            runnable(n)   
            // must test TRUE against all prior machines in the list   
            && min_tc_subset.all(m -> not_func_eq(m,n)   
          )   
            min_tc_subset.push(n)   
        }   
      }   
      
      
   --   
   arising us out of the computing dark ages,   
   please excuse my pseudo-pyscript,   
   ~ nick   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)