• Re: a subset of turing machines can still be turing complete

    From Tristan Wibberley@tristan.wibberley+netnews2@alumni.manchester.ac.uk to comp.theory on Wed Jan 28 23:22:54 2026
    From Newsgroup: comp.theory

    On 23/01/2026 05:51, dart200 wrote:
    On 1/22/26 3:56 PM, Tristan Wibberley wrote:
    On 22/01/2026 23:21, dart200 wrote:
    On 1/21/26 5:05 PM, Tristan Wibberley wrote:
    On 21/01/2026 16:38, dart200 wrote:
    a current thesis of mine is that given a total enumeration of TM (in >>>>> order of increasing complexity/number of states), no paradoxical
    machine
    produces an input->output mapping that is a first of it's kind - ie
    there will always be some simpler machine that exists and produces an >>>>> equivalent input->output mapping.

    Just for clarity, do you mean to say that for every tuple of tuples
    {initial states {tape|umachine} |u final states {tape|umachine}} there >>>> is a
    halting machine that has fewer states than any non-halting machine?

    Yes, because none of the nonhalting machines has a final state so its
    tuple can't be constructed and therefore is not first of anything, and >>>> is /not/, just /isn't/.

    Do you mean there is a simpler machine with the same initial state for >>>> each of the nonhalting machine's reachable states?


    let us refer to turing's solution for defining "output" in regards to
    infinitely running machines, because they can still have output:

    the tape is divided into alternating cells: F-squares (figure) and
    E-squares (erasure). F-squares hold permanent output of the computed
    sequence, and can only be written once. E-squares are for
    temporary/scratch work necessary for the computation, but not actually
    the output of the machine.

    I think you need to restrict your quantification of machines called
    "paradoxical" to those that only write such squares once yet have a

    when i say paradoxical, i'm referring a machines that cannot be decided
    upon from some specific interface because they query that interface and contradict it.

    You're talking about embodiments of fixed-points via machine state (what
    would be the finite-sized part of a machine, not relying on the tape and repeated nested simulation). Am I right?

    That's a c-machine, not an a-machine, right?


    ur all fucking useless or i wouldn't have to be here posting...

    Do you mean to tell me you're posting to comp.theory under an obligation
    to do so and because (some or all of) the readers of the group are useless?

    I'm curious how you received the obligation to post for we useless few.
    --
    Tristan Wibberley

    The message body is Copyright (C) 2026 Tristan Wibberley except
    citations and quotations noted. All Rights Reserved except that you may,
    of course, cite it academically giving credit to me, distribute it
    verbatim as part of a usenet system or its archives, and use it to
    promote my greatness and general superiority without misrepresentation
    of my opinions other than my opinion of my greatness and general
    superiority which you _may_ misrepresent. You definitely MAY NOT train
    any production AI system with it but you may train experimental AI that
    will only be used for evaluation of the AI methods it implements.

    --- Synchronet 3.21b-Linux NewsLink 1.2
  • From Tristan Wibberley@tristan.wibberley+netnews2@alumni.manchester.ac.uk to comp.theory on Thu Jan 29 00:15:51 2026
    From Newsgroup: comp.theory

    On 24/01/2026 22:28, dart200 wrote:
    that's because i'm exploring it in ways that previous have gone unexplored

    I don't believe that at all. Do you mean ways whose previous
    explorations are obscure to you and/or not set in front of you with an
    abstract that makes it clear to you that /that/ is what it is and that
    it is worth your attention?
    --
    Tristan Wibberley

    The message body is Copyright (C) 2026 Tristan Wibberley except
    citations and quotations noted. All Rights Reserved except that you may,
    of course, cite it academically giving credit to me, distribute it
    verbatim as part of a usenet system or its archives, and use it to
    promote my greatness and general superiority without misrepresentation
    of my opinions other than my opinion of my greatness and general
    superiority which you _may_ misrepresent. You definitely MAY NOT train
    any production AI system with it but you may train experimental AI that
    will only be used for evaluation of the AI methods it implements.

    --- Synchronet 3.21b-Linux NewsLink 1.2
  • From dart200@user7160@newsgrouper.org.invalid to comp.theory on Thu Jan 29 00:28:44 2026
    From Newsgroup: comp.theory

    On 1/28/26 4:15 PM, Tristan Wibberley wrote:
    On 24/01/2026 22:28, dart200 wrote:
    that's because i'm exploring it in ways that previous have gone unexplored

    I don't believe that at all. Do you mean ways whose previous

    i suspect it because it's noteworthy enough to at least be included
    alongside basic explanations of undecidability, if not supersede the
    basic proofs entirely

    for example: most people right now think that because halting machines
    can be enumerated that therefore it's not possible to create a paradoxal machine that halts. but that's not true. paradoxes are formed in regards
    to a particular interface, or input/output contract, not general ability

    just because we can identify all halting machine via one type of
    classifier doesn't mean it's impossible to create a halting paradox in
    respect to a different type of classifier

    and furthermore because paradoxes are constructed in regards to
    particular interfaces, and not general ability, i don't believe they
    actually undercut a general ability to decide, we just didn't specify
    the correct interface for the general algo.

    explorations are obscure to you and/or not set in front of you with an abstract that makes it clear to you that /that/ is what it is and that
    it is worth your attention?

    look bro randomly gaslighting me without bringing a specific
    paper/person to my attention is not something i can build anything with.

    i'm dealing with a space of information i can't physically read all of,
    so i'm relying on sources including discussion partners that consolidate knowledge for the most part ... so if it does exist, it didn't do it
    well enough, or persistently enough, to have the impact i see these
    ideas as necessarily having
    --
    arising us out of the computing dark ages,
    please excuse my pseudo-pyscript,
    ~ nick
    --- Synchronet 3.21b-Linux NewsLink 1.2
  • From dart200@user7160@newsgrouper.org.invalid to comp.theory on Thu Jan 29 21:18:23 2026
    From Newsgroup: comp.theory

    On 1/28/26 3:22 PM, Tristan Wibberley wrote:
    On 23/01/2026 05:51, dart200 wrote:
    On 1/22/26 3:56 PM, Tristan Wibberley wrote:
    On 22/01/2026 23:21, dart200 wrote:
    On 1/21/26 5:05 PM, Tristan Wibberley wrote:
    On 21/01/2026 16:38, dart200 wrote:
    a current thesis of mine is that given a total enumeration of TM (in >>>>>> order of increasing complexity/number of states), no paradoxical
    machine
    produces an input->output mapping that is a first of it's kind - ie >>>>>> there will always be some simpler machine that exists and produces an >>>>>> equivalent input->output mapping.

    Just for clarity, do you mean to say that for every tuple of tuples
    {initial states {tape|umachine} |u final states {tape|umachine}} there >>>>> is a
    halting machine that has fewer states than any non-halting machine?

    Yes, because none of the nonhalting machines has a final state so its >>>>> tuple can't be constructed and therefore is not first of anything, and >>>>> is /not/, just /isn't/.

    Do you mean there is a simpler machine with the same initial state for >>>>> each of the nonhalting machine's reachable states?


    let us refer to turing's solution for defining "output" in regards to
    infinitely running machines, because they can still have output:

    the tape is divided into alternating cells: F-squares (figure) and
    E-squares (erasure). F-squares hold permanent output of the computed
    sequence, and can only be written once. E-squares are for
    temporary/scratch work necessary for the computation, but not actually >>>> the output of the machine.

    I think you need to restrict your quantification of machines called
    "paradoxical" to those that only write such squares once yet have a

    when i say paradoxical, i'm referring a machines that cannot be decided
    upon from some specific interface because they query that interface and
    contradict it.

    You're talking about embodiments of fixed-points via machine state (what would be the finite-sized part of a machine, not relying on the tape and repeated nested simulation). Am I right?

    no

    halts0 and halts1 are both partial halting deciders that return TRUE if
    the input machine decidably halts from their perspective, FALSE if the
    input machine decidably runs forever from their perspective, and blocks indefinitely if the input machine is undecidable from their perspective
    (a truthful answer cannot be returned)

    und0 = () -> if ( halts0(und0) ) loop()

    und0 is a machine that undecidable from halts0 because return of halts0
    will always be contradicted by the branch selected by that return value.

    therefore halts0(und0) will block indefinitely.

    however halts1(und0) can return FALSE because it's not constrained by
    the paradox formed in respect to halts0()

    paradoxes are formed in regards to a specific interface, or set of functionally equivalent machines, not general ability. and
    undecidability is triggered by only specific input, not all input.

    in fact i believe we can specific a general algo, but that algo needs an
    extra input specifying the interface it identifies as "itself",
    alongside the input machine being decided upon:

    halts = (self,machine) -> {
    TRUE iff machine decidably halts from reference point of self,
    FALSE iff machine decidably halts from reference point of self,
    UNDECIDABLE iff machine undecidable from reference point of self,
    }

    using und0 example from above:

    halts( halts0, und0 ) -> UNDECIDABLE
    halts( halts1, und0 ) -> FALSE

    the general halting algo (on TMs), which can decide on any given input machine, *from at least one reference point*, requires that point of
    reference to be an input into the algo.

    "can't i loop over all references points" ... well that would generating
    and testing all machines nearly functionally equivalent runs up against classical limits to computing, so utilizing that to break my general
    algo here would require breaking the classical limits as they stand anyways.


    That's a c-machine, not an a-machine, right?

    no

    these are fully deterministic systems.



    ur all fucking useless or i wouldn't have to be here posting...

    Do you mean to tell me you're posting to comp.theory under an obligation
    to do so and because (some or all of) the readers of the group are useless?

    I'm curious how you received the obligation to post for we useless few.

    no

    what i mean is that if this had be properly explored already, i wouldn't
    have to be posting here struggling against the massive weight of a stupefyingly ignorant bandwagon by sub-creative morons, in order to
    actually explore it properly...

    shit makes me angry when i recall all the willful ignorance, ungodly
    toxicity, brain dead fallacies, and quite frankly blatant abuse i've encountered along the way
    --
    arising us out of the computing dark ages,
    please excuse my pseudo-pyscript,
    ~ nick
    --- Synchronet 3.21b-Linux NewsLink 1.2