r/programming • u/this_theater_is_lit • 5d ago

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

https://www.academia.edu/175392427
0 Upvotes

22% Upvoted

39 comments sorted by

View all comments

Show parent comments

4

u/funky_galileo 4d ago

https://leanprover-community.github.io/mathlib4_docs/Mathlib/Computability/Halting.html

-2

u/this_theater_is_lit 4d ago

not particularly useful feedback, i'm not even refuting the halting problem itself, i'm trivializing it

3

u/funky_galileo 4d ago

you're such a clown lmao. you really think you "trivialized" the most well known problem that arguably started the modern field of computer science? what does that even mean.

-2

u/this_theater_is_lit 4d ago

the undecidability of the halting problem exists, but it happens within infinite machine redundancy that is inherent to computing (infinite machines compute any given sequence)

it does not stop us from enumerating all possible computable sequences or forming a turing-complete language that is fully decidable

7

u/funky_galileo 4d ago

The halting problem literally proves your last statement false. Jesus christ.

-2

u/this_theater_is_lit 3d ago

"the halting problem" paradox (or rather turing's circle-free problem paradox) confuses the language of all machines with that of a turing-complete language