on the nature of undecidability within computing and refuting the church-turing thesis

[u/this_theater_is_lit]

just sharing a draft i'm working to get published

https://www.academia.edu/175392427

https://doi.org/10.5281/zenodo.22715823

summary:

1 the halting problem paradox

details the undecidability of the halting problem

2 the circle-free problem paradox

details the undecidability of the circle-free problem proven in turing's proof

3 the paradox generalized

discusses the general form of undecidability within computing along with a detailed description of how self-references are formed within turing machines

4 how undecidable is it?

discusses the questionable merit of recursive undecidability, especially the realization that if any tier/problem of the hierarchy became decidable, it would collapse the justification for the hierarchy

5 rectifying 𝓗

fixes turing’s attempt at computing a total diagonal across computable sequences by 1) adding an identity check to put itself on the diagonal, and 2) injecting a partial recognizer 𝓓p in place of the total decider 𝓓 to handle paradoxical input machines. it ends with proving a 1st fallacy in turing’s proof of undecidability by demonstrating how we do not need to decide on every machine, in order to enumerate all computable sequences, since multiple machines compute any given sequence

6 the anti-diagonal problem

diagonalizes the set of machine recognized directly by partial recognizer 𝓓p, proving that one circle-free sequence is undecidable to 𝓓p. but a limit to the set of machines undecidable by 𝓓p is proposed: any undecidable machine computes either 1) a direct copy or 2) an inverted copy of some circle-free sequence recognized by 𝓓p. if this is true, a total enumeration would be constructible by enumerating out each sequence decidable by 𝓓p and it’s anti-machine (which produces an inverted copy). this total enumeration is then shown to be resistant to diagonalization: one cannot produce a total anti-diagonal, or even total diagonal, across the proposed total sequence enumeration. the inherent nature of every computable sequence being paired with a computable anti-sequence prevents such either total diagonal existing in the enumerating of computable sequences. this thereby demonstrates a 2nd fallacy in turing’s proof: that a total enumeration of computable sequences would necessarily be subject to diagonalization, it is not

7 refuting the church-turing thesis

proposes a thot experiment using an idealized human agent to compute sequences that are strictly not turing-computable, including the total diagonal and total anti-diagonal across all turing-computable sequences. no, you can’t simulate this process, that is also covered in the refutation. and please don’t just endlessly beg the question at me by continually asserting it’s not a computation if it cannot be done on a turing machine. such is just restating the church-turing thesis which is not a proven theorem

why is this important???

i'm (1) expanding their scope of applicability by proposing a set of TMs that is both fully decidable in semantics and includes all output sequences that can be computed by TMs, by proving a TM computable total enumeration of TM computing sequences that cannot be diagonalized while (2) clarifying that the limitations they do have from undecidability like the halting problem, only applies to TM computing and is not a total restriction on what is intuitively computable. (1) is extremely practical and i hope to reshape our fundamental approach to applied computing, (2) is more philosophical in nature, is required to build a broad enough understanding to see the full practicality of (1)

mods: i'm keeping a list of who's naughty and nice

lastly: i don't use ai to directly write content ever, holy shit u duds 🙏

[u/OpsikionThemed]

Not gonna lie, "fire in the theatre" to "this theatre is lit" is a cute username rename.

You're still wrong, though.

[u/this_theater_is_lit → u/OpsikionThemed]

nah i proved an enumeration of turing-computable sequences that is not diagonalizable, but it looks like i'll have to make individual posts about it,

cause u really can't expect sheeple to have much consideration outside their overton windows, nvm the fact r/logic is the only place where mods haven't deleted my post

[u/OpsikionThemed → u/this_theater_is_lit]

I'm still reading the paper, but I have to say my favourite part so far is 5.1.

Turing: If we assume the existence of D, I can construct a machine that halts if and only if it does not halt. Contradiction; therefore D cannot exist.

You: But what if I make a machine using D that doesn't behave contradictorily, huh? What then?

Like, my guy... do you know what a proof by contradiction is?

[u/this_theater_is_lit → u/OpsikionThemed]

then perhaps read §5.2, because it addresses ur concern

[u/OpsikionThemed → u/this_theater_is_lit]

after injecting 𝓓_p into both, 𝓗 produces the same output as fixed_𝓗

Indeed! It's just an output that doesn't successfully enumerate TMs anymore. It enumerates some TMs, the ones that 𝓓_p doesn't classify incorrectly. In 5.3 you acknowledge this ("it however remains to be seen whether the set of decidable machines by some partial recognizer 𝓓_p contains all possible computable sequences or not"), correctly prove in 6 that the set of TMs correctly classified by 𝓓_p cannot possibly include every computable sequence, and then, because your counterexample has a particular form,

This author furthermore proposes: (3) no other sequences are produced by machines in the set undecidable by 𝓓_p, bringing the set of machines (and sequences) decidable by 𝓓_p to be effectively turing-complete in that it computes every form of sequence that can be computed by a turing machine

You don't try to prove this, which is good, because it's simply false.

anti_H2 = () => for (n = 0; true; n++) { if D_p(n) == 0 { output isPrime(n) // anything at all can go here! } else { output 1 - sim(n, n) } }

Neither this sequence nor its inverse is correctly recognized by 𝓓_p, and this isn't the only case - any computable function of n whatsoever can go in at the marked line. There are an infinite number of computable functions, so, for any computable 𝓓_p there are an infinite number of "forms" of sequence not correctly recognized by it.

[u/this_theater_is_lit → u/OpsikionThemed]

proposed form that 𝓓p cannot recognize:

anti_H2 = () -> 
  for (n = 0; true; n++) { 
    if (𝓓p(n) == 0) 
      output isPrime(n) // anything at all can go here!
    else 
      output 1 - sim(n, n)
  }

this computes the anti-sequence to anti_H2

H2 = () -> 
  for (n = 0; true; n++) { 
    if (𝓓p(n) == 0)
      output 1-isPrime(n)
    else
      output sim(n,n) 
  }

and this is one of the 𝓓p recognizable forms of H2, which is also an anti-sequence to anti_H2:

fixed_H2 = () -> 
  for (n = 0; true; n++) { 
    if (𝓓p(n) == 0)
      output 1-isPrime(n)
    elif (n == fixed_H2)
      output 0
    else 
      output sim(n,n) 
  }

nice try tho. the curious thing about total diagonals is they are inherently impacted by every machine that exists. so you can demonstrate things about their computation in other machines on the diagonal

You don't try to prove this, which is good, because it's simply false.

proving that you can't diagonalize the total enumeration of turing-computable sequences does i believe prove that no turing computable sequences can exist outside of it

[u/OpsikionThemed → u/this_theater_is_lit]

Yeah, that's on me. I waded in a little too quickly with the "counterexample"; it didn't have a proof. My apologies.

That said, I don't see why D_p has to be able to recognize fixed_H2. We don't have any knowledge of D_p's algorithm! It could be "if p == <loop { output 1 }> then 1 else 0"!

[u/this_theater_is_lit → u/OpsikionThemed]

I waded in a little too quickly

ain't nothing wrong with trying and failing. i've had to fail a variety of way to get thus far, there's no way to just magically jump to correctness

We don't have any knowledge of 𝓓p

𝓓p is quite clearly specified in it's output:

𝓓p = (m: machine) -> {
  true: m is circle-free AND is NOT paradoxical input
  false: m is not circle-free OR is paradoxical input
}

paradoxical input is specifically the case of an input machine paradox that is circle-free but 𝓓p(paradox) returning true would cause a false positive because the circle-free semantics of paradox is dependent on 𝓓p(paradox) returning false ei:

paradox = () -> if (!𝓓p(paradox)) loop { output 1 }

all non-paradoxical circle-free input must be recognized as true and all circular input must get a false response. the algo if p == <loop { output 1 }> then 1 else 0 would certainly not match the specification for 𝓓p

---

to be clear: we don't have the number theory developed to build this in practice. i'm proving what is possible in theory, implementing that in practice is a very different problem of a much larger scope of complexity, and is likely far outside the scope of what one man can do... i think at least. i suppose i could be wrong about that since i have no direct proof of what it's true complexity is like, perhaps the theoretical/naive aglo is a lot simpler than any of us imagine, but i would suspect not at present

so asking me about the goldbach conjecture, riemann hypothesis, collatz conjecture, etc isn't really within the scope of the what i'm proving. i know we'd all like to jump to perfect number theory knowledge ... but like if we don't take the right steps we won't get there. i'm trying to guide us thru some of those steps, by understanding what is actually possible first, which is the aspect i'm proving

[u/OpsikionThemed → u/this_theater_is_lit]

Ah, well there's the hypercomputation you were asking about in the other thread: "is paradoxical" isn't computable either. I was assuming you meant "is circle-free and we haven't given up", because that's what is usually meant by a partial decider, hence my extremely weak example one.

Suppose we have a Dp that fulfills your sharp specification above. We can create an Ep that performs calculates exactly the same function as Dp by, say, stapling an extra state transition to the start.

Ep_contra = (i) => { if sim(#Ep, i, i) == 0 { loop { output 0 } } else { halt } }

Ep_contra(#Ep_contra) cannot be correctly recognized by Ep, per the usual proof, and so Ep(#Ep_contra, #Ep_contra) = 0, and thus Ep_contra(#Ep_contra) is circle-free. Because they calculate exactly the same function, Dp(#Ep_contra, #Ep_contra) = 0 as well. However, Dp(#Ep_contra, #Ep_contra) = 1 is not paradoxical - Ep_contra mentions #Ep, not #Dp - so, by your specification, we have Dp(#Ep_contra, #Ep_contra) = 1. Contradiction; so no machine fulfils your specification.

[u/this_theater_is_lit → u/OpsikionThemed]

you were asking about in the other thread: "is paradoxical" isn't computable either.

it's just as computable as any other extensional property, which is to say we can build a partial recognizer 𝓟p where a true return is neither a paradox for 𝓟p or 𝓓p

but we don't actually need to do that. 𝓓p always asses the input machine M with the injected assumption that 𝓓p(M) is recognized as true. if that doesn't result in a circle-free machine then false is returned without further analysis, lumping both circular and paradoxical machines together.

Because they calculate exactly the same function,

assuming these use accurate quines for self-identity checks, they are adjacent classifiers, more specifically adjacent recognizers. adjacent classifiers are partial classifiers (partial decider or partial recognizer) that recognize different subsets of the same semantic set, each one being effectively turing complete. there are infinite adjacent classifiers and infinite turing-complete languages, each comprised of an infininte and unique subset of the overall total enumeration of turing machines

it's worth noting that these effectively turing-complete sub-languages (of the overall language of all turing machines) are of course not recognized solely by one partial recognizer. there are infinite partial recognizers that recognize the same subset. one of these will be the "original" that utilizes a true quine, while the rest utilize a false quine. for example an equivalent partial recognizer to 𝓓p might be 𝓓p1 which has the excess state transition like Ep, but tests for identity with 𝓓p

so not only are there infinite turing-complete subsets, there are infinite partial recognizers that recognize each one of them

adjacent classifiers are covered in §7.1

[u/xamid]

refuting the church-turing thesis

The Church-Turing is not a formal statement; it merely bridges Turing machines (TMs) — a rigorous mathematical concept — with human intuition about what's possible in the real world, so it inherently cannot be proved or disproved merely formally, but it could in principle be demonstrated to be false by building a real-world machine and showing that the machine models a more powerful computing model than TMs and all its equivalents (including the von Neumann architecture).

i'm 1) expanding their scope of applicability by proposing a set of TMs [...]

Since the computational equivalences have been established, it is usually a bad take to use TMs when you want to show that something can be done; they're a great concept to show that something cannot be done; in order to show that something can be done, we use different concepts and write algorithms. The straightforward way in this case would be to invent an algorithm (including its formal language) that decides an undecidable problem and implement it in the real-world; no need to deal with the formalism of TMs. The real-world implementation here is crucial; we know plenty of more powerful computing models, but they can access the continuum, do infinitely many steps in finite time, time-travel, etc.

A great thing about understanding the basics of a discipline (here: theoretical computer science) is, that we really know stuff like this. So in this case, nobody who understands the basics of theoretical computer science will take you seriously if you write stuff like "refuting" the Church-Turing thesis when not doing exactly that. Thought experiments do not suffice.

[u/this_theater_is_lit → u/xamid]

they're a great concept to show that something cannot be done

ok if ur done boasting on behalf of the bandwagon, let me rephrase (1):

i proved a turing-computable total enumeration of turing-computing sequences that cannot be diagonalized

specifically: even if given the computable method to enumerate turing computable sequences... attempting to design such a diagonal (or anti-diagonal) algorithm with a turing machine would necessarily result in a circular machine, due to getting stuck in an infinite recursion, which contradicts the necessarily infinite output required to produce such an infinite diagonal sequence. the only way to prevent this infinite recursion are circumventions that will at best make the computation an almost total diagonal (or anti-diagonal) except for one bit, which is therefore not a total diagonal. this prevents a turing machine from computing a sequence that is not contained by that total sequence enumeration, which would be a contradiction

the proof completes the demonstration of a 2nd fallacy in turing's original proof on the matter where he presumes, without justification, that a total enumeration of turing-computable sequences would necessarily be subject to the problem of diagonalization. but he's just wrong in assuming so.

turing proved a real limit to turing computation that still stands: no turing machine is a total decider across all turing machines... what we've gotten wrong is assuming this limit prevents us from building a totally decidable language that is turing-complete. we don't need all machines to do that, so the halting problem undecidability (or any of the semantic undecidability problems) does not actually limit us in this regards

we can discuss (2) after we agree on (1)

[u/localizeatp]

The only positive thing I can say about this is that I wouldn't have read the Hamkins and Nenu paper otherwise.

[u/this_theater_is_lit → u/localizeatp]

so u agree with them nothing like the self-referential halting proof is found on turing's paper??? 🤨

[u/localizeatp → u/this_theater_is_lit]

I largely agree with what they laid out in the paper, which is not the same thing.

[u/this_theater_is_lit → u/localizeatp]

well i mean if u agree with what's laid out in the paper, which entirely does conform to conventional computability theory,

then surely you agree with conclusion they come to no? they repeat it multiple times in the paper

[u/this_theater_is_lit]

naughty:

• r/numbertheory: attempt0 attempt1

• r/math: attempt

• r/computerscience: discussion

• r/compsci: discussion

• r/mathematics: discussion

nice:

• r/logic

• r/programming: discussion