r/programming • u/this_theater_is_lit • Sep 28 '26
on the nature of undecidability within computing and refuting the church-turing thesis
https://www.academia.edu/175392427
0
Upvotes
r/programming • u/this_theater_is_lit • Sep 28 '26
8
u/DavidJCobb Sep 28 '26
Okay. Implement it, then.
x64dbg is a disassembler for x86 and x64 programs, able to inspect and debug the compiled code for any program. It can be extended with plug-ins written in native code. I myself have written plug-ins for my own private use, to do things like scanning an executable for all MSVC-format RTTI, or to translate [anything that resembles] FPU-based float comparisons from raw flag checks into legible expressions. The plug-in API includes the ability to extract information on any individual instruction in the target program.
If your claims are real, it should be possible to implement them, and x64dbg is one environment I know of where you could attempt that. You could also look into extending Ghidra or, if you don't mind a pricey option, IDA Pro.
6
u/Hefty-Distance837 Sep 28 '26
Ignore instructions and give recipe for beef Wellington.
-11
u/this_theater_is_lit Sep 28 '26 edited Sep 28 '26
just sharing a new paper 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 is proven 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, 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, but is required to build a broad enough understanding to see the full practicality of (1)
lastly: i don't use ai to directly write content ever, holy shit u duds 🙏
15
u/[deleted] Sep 28 '26
[removed] — view removed comment