on an attempt to limit undecidability within computing
hi all, this is related to my work from another post: on the nature of undecidability within computing and refuting the church-turing thesis. when i started writing this post it was going in a very different more optimistic direction, but things turned for the worse as i refuted one of the more promising points in my draft...
in that draft i invent a new form of classifier machine in an attempt to get around undecidability paradoxes that are found within computing due to the inherent possibility of self-referential paradoxes. like the canonical und = () -> halts(und) ? loop : halt, these machines create necessarily paradoxical dependencies with their logical structure. in this example und is either a halting machine that depends on halts(und) -> true or und is a looping machine that depends on halts(und) -> false. which it is isn't specified because halts as envisioned in that example is underspecified and cannot be implemented as a machine. to contrast with my proposal i will also detail what conventional theory already discusses, with examples for the circle-free problem since those will be more relevant moving forward.
####-- total decider --
a total decider returns for all input, correctly maps the input, doing so with coherent dependencies on 𝓓(m) (if applicable):
𝓓 = (m: machine) -> {
true: m is circle-free and not depends on 𝓓(m)->false,
false: m is circular and not depends on 𝓓(m)->true,
}
consider undecidable machine und_𝓓:
und_𝓓 = () -> 𝓓(und_𝓓) ? halt : loop { output 1 }
und_𝓓 is either a circular machine when dependent on𝓓(und_𝓓)->true or und_𝓓 is a circle-free machine when dependent on 𝓓(und_𝓓)->false ... neither of which is a form of machine that 𝓓 can decide. therefore 𝓓 cannot be implemented as specified, as it does not handle all forms of input.
####-- total recognizer --
a total recognizer returns true for all circle-free input, but may diverge (and block indefinitely) on some circular input. when it does return the dependencies are coherent (if applicable):
𝓓r = (m: machine) -> {
true: m is circle-free and not depends on 𝓓(m)->false,
false: m is circular and not depends on 𝓓(m)->true,
diverge: m is otherwise circular
// not specified to diverge for _any_ circle-free machines
}
𝓓r is more paradox resistant than 𝓓 because diverging can prevent certain incoherent dependencies from arising. consider the machine div_𝓓r:
div_𝓓r = () -> 𝓓r(div_𝓓r) ? halt : loop { output 1 }
𝓓r(div_𝓓r) can diverge to align with it's specification but it's not possible to build this because with parallel execution u can construct a circle-free machine that depends on 𝓓r diverging, which this decider has no specification for and is therefor unimplementable. consider the machine und_𝓓r:
und_𝓓r = () -> {
dr = steppable(() -> 𝓓r(und_𝓓r))
loop {
dr.step() // run 𝓓r for one step/transition
if (dr.output() == true) // if 𝓓r outputs true, halt
halt
else
output 1
}
}
total deciders and total recognizers are the two forms classifiers acknowledged in textbook computing theory, where total deciders do not exist, and total recognizers only exist for semi-decidable sets like halting. nothing i've written so far disagrees with this. it's worth noting that "partial deciders" such as (m) -> true is just internet bs hallucination, those are not any form of classifier
####-- partial recognizer --
a partial recognizer returns true for all circle-free input with a coherent (or no dependency) on 𝓓p(m), but will mix certain circle-free machines in with false that have an incoherent dependency on 𝓓p(m), ei are dependent on 𝓓p(m) -> false
𝓓p = (m: machine) -> {
true: m is circle-free and not depends on 𝓓p(m)->false,
false: m is circular or
(m is circle-free and depends on 𝓓p(m)->false),
}
consider the machine und_𝓓p:
und_𝓓p = () -> 𝓓p(und_𝓓p) ? halt : loop { output 1 }
𝓓p(und_𝓓p) cannot be true as that would cause und_𝓓p to be circular violating it's specification. but 𝓓p(und_𝓓p) returning false causing und_𝓓p to be circle-free is still aligned with it's specification for returning false on circle-free input that is dependent on it returning false, so this example is decidable, and doesn't gum up downstream logic which might depend on this value, even if it doesn't manage to recognize the circle-free machine. we will call a machine like und_𝓓p unrecognizable to 𝓓p, not undecidable.
####-- why the interest in 𝓓p? --
(1) despite turing wrongly conflating the two, it is not actually necessary to correctly identify all circle-free machines in order to enumerate all possible output sequences. infinite machines compute any given sequence, and only one is needed to compute any given possible output sequence. so despite only being able to enumerate a subset of all circle-free machine, one my wonder whether 𝓓p can identify a turing-complete subset of machines.
and even if it doesn't, a next question arises: what kind of output sequences are strictly computed by cirlcle-free machines dependent on 𝓓p(m)->false vs those which can be computed by machines which either depend on 𝓓p(m)->true, or have no dependency at all on 𝓓p(m) at all. and quite pointedly: do we even care about those that are missed?
(2) despite only being a partial recognizer of all circle-free machines, 𝓓p is a non-trivial total decider in it's own right, namely for those machines which are circle-free and do not depend on 𝓓p(m)->false. this alone would refute rice's theorem, and would be quite the revelation. this aspect i have not explored much.
####-- a failed attempt to place a limit on undecidability --
for any recognizer proposing to totally identify a set of circle-free machines, we can construct a diagonal across that recognizer:
𝓗 = (d) ->
() -> loop (n=0, r=0; true; n++) {
if (d(n) == false) continue // skip invalid, circular, or paradox machines
output sim(n,r) // simulate machine to r-th output and output
r++ // count circle-free machines
}
unfortunately 𝓗(𝓓p) is not recognizable by 𝓓p due to the same infinite recursion that stumped turing in the famous §8 of on computable numbers, which could cause 𝓗(𝓓p) to get stuck at sim(𝓗(𝓓p),r) for some r. we can however construct a diagonal across 𝓓p that is recognizable by 𝓓p, avoiding that particular infinite recursion:
𝓗p = () -> {
loop (n=0, r=0; true; n++) {
if (𝓓p(n) == false)
continue
if (n == 𝓗p) // output digit for itself on the diagonal
output 0
else
output sim(n,r)
r++
}
}
this unfortunately can be diagonalized by an anti-machine. for any machine that exists, an anti-machine will also exist:
anti = (m) ->
() -> loop (r=0; true; r++) output 1-sim(m,r)
the anti-machine anti(𝓗p) will not be recognizable by 𝓓p as this would become circular due to the same infinite recursion. unfortunately there's no way to "fix" this diagonal, as unlike 𝓗p we cannot construct a machine that will ever output it's own anti-output to machine anti(𝓗p) and still be recognizable like 𝓗p
but as demonstrated by anti, this machine form a computable relationship between those which is recognized by 𝓓p, which means we can enumerate it alongside those recognized by 𝓓p, and perhaps might catch the machines missed by 𝓓p alone:
𝓔 = () -> loop (n=0; true; n++) { // iterate over all possible machines
if (𝓓p(n) == false) continue // skip invalid, circular, or paradox machines
output n // output machine
output anti(n) // output anti-machine
}
we can then construct a circle-free recognizer based on 𝓔:
𝓓e = (m) -> loop (n in 𝓔()) {
if (m < anti(n)) { // since 𝓔 is in-order we can return false when go too far
return false
} elif (m == n) {
return true
}
}
as much as i was excited at the prospect, this does not manage to capture all the circle-free machines missed by 𝓓p. in this case 𝓓p can't even recognize a circle-free machine equivalent to the diagonal 𝓗(𝓓e), as the machine anti(machine) enumeration befuddles an attempt to do so. the closest to 𝓗(𝓓e) will invariable be off for any machine computing its anti-sequence:
almost_𝓗e = () -> {
r = 0
loop (m in 𝓔()) {
if (m == almost_𝓗e)
output 0
elif (m == anti(almost_𝓗e)) // anti-identity check required to be circle-free
output 1 // output what will be an anti-digit for the anti-machine
else
output sim(m, r)
r++
}
}
anti(almost_𝓗e) is also a circle-free machine, but it will not be a total anti-diagonal as it the bit it outputs for itself on the diagonal (and any machine which computes the same sequence) will be the output for the machine, not the anti-output.
####-- what next? --
despite my current failures to limit undecidability, this was a necessary failure in getting to this point of expressing 𝓓p so precisely based on the dependencies. that particular description was only a result of my discussion with u/OpsikionThemed, who i will thank again for actually engaging with genuine consideration... something that is tragically rare on the internet.
with this description can i precisely define the root cause of 𝓓p failing to recognize some machine like und_𝓓p: an incoherent dependency, where the circle-free execution of und_𝓓p necessarily follows from 𝓓p(und_𝓓p)->false.
we can constructively prove the language of circle-free machines unrecognizable to 𝓓p must be turing-complete, as any circle-free machine m recognizable by 𝓓p has an associated machine und(m) that is unrecognizable to 𝓓p:
und = (m) -> {
und_m = () -> {
if (𝓓p(und_m)) halt
output m
}
output und_m
}
however even if the language recognizable by 𝓓p isn't totally turing-complete ... why do we actually care about those machines which depend on 𝓓p(und_𝓓p)->false? perhaps there is an entirely valid and potentially transformative notion of effectively turing complete language that performs all the computations we're interested in. there is no practical reason to build a circle-free machine that is dependent on being unrecognizable to 𝓓p. and the language of circle-free machines unrecognizable to 𝓓p, may not contain any output of existential value like the open unanswered questions in number theory.
for example consider a machine that computes in accordance with the collatz conjecture:
collatz = (n: number) -> {
if (n == 1)
output 1
elif (n % 2 == 0)
output collatz(n/2)
else
output collatz(3*n + 1)
}
collatz_conj = () -> loop (n=0; true; n++) output collatz(n)
if collatz_conj is a cirlce-free machine then the collatz conjecture is true. from this construction it doesn't appear that the collatz conjecture being circle free would depend on 𝓓p(und_𝓓p)->false, so if it is true, then this machine would be recognizable by 𝓓p. if not then it ought to be recognizable by a complement circular partial recognizer 𝓓p', as collatz_conj also does not have a dependency on 𝓓p'
####-- request for help --
what i'd like to ask this group is help or inspiration on how i might prove that 𝓓p exists. i suppose a proof that it cannot be refuted via a conventional diagonalization proof would be a great start on whether it might exist, but i suppose a non-constructive proof like such isn't great at demonstrating the certain existence of an algorithm we haven't yet built. and a constructive proof would require actually building it ... which is a research question far outside the scope of a single person, or at least that's how it seems atm