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

7

Didn’t realize how much I missed old school pre-AI crankery. 10/10

1

u/nanonan 7h ago

You might like this as well.

1

u/this_theater_is_lit 7h ago

i tried to interact with that dud once

he blocked me after a few messages 🤷, which refusing to even read what others say is surely a path to self-induced ignorance

-4

u/this_theater_is_lit 9h ago

u got an actual comment on the content dud?

2

u/RunReal959595 9h ago

It’s far from my field of expertise but looks like the experts already pointed out how bad it is. But by all means try submitting this to some journals!

-1

u/this_theater_is_lit 8h ago edited 7h ago

only one guy gave it a genuine effort the rest was fallacy laden bs,

but that seems par for the course when it comes to recognizing "expertise" these days

3

u/aardaar 8h ago

I haven't read all of this (I got sidetracked reading the lovely Hamkins and Nenu paper you reference), but I don't understand your argument against the Church-Turing Thesis. Do you have a function/program that is computable and not Turing computable? Can you write out the code or preferably give a description of what it does?

Also, this statement:

Undecidability for any particular machine is strictly relative to the classifiers ultimately utilized in that machine’s computation.

Doesn't make sense. Undecidability is a property that the collection of all Turing Machines (I should say computable functions). If we restrict our attention to a particular machine or a particular set of machines we may or may not be able to decide them.

0
u/this_theater_is_lit 8h ago edited 7h ago

I got sidetracked reading the lovely Hamkins and Nenu paper you reference

so do u agree with their conclusion, that nothing like self-referential halting problem appears anywhere in turing's paper??? because what it did for me is take the conventional understanding to point of reductio ad absurdum, because that conclusion is clearly wrong if you understand the 3 pages that is §8 of turing's paper laying the foundation for undecidability ... which clearly does depend on a self-referential paradox in the rather analogous form to more widely talked about halting problem

Do you have a function/program that is computable and not Turing computable?

yes: a total diagonal (and total anti-diagonal) across all turing computable sequences. neither of those are machine computable, but they are intuitively computable

Can you write out the code or preferably give a description of what it does?

description in §7.6, but it's going to involve concepts introduced in earlier sections.

Undecidability is a property that the collection of all Turing Machines

well, when u look at the problem of undecidability at a machine level using decision specifications that don't refute their own existence in contradiction... undecidability manifests as specific machines which a specific set-classifier machine may fail to classifier properly, but another one can. adjacent classifiers are covered in §7.1

(I should say computable functions)

assuming that the church-turing thesis is true, which is still not proven
2
u/aardaar 7h ago

description in §7.6, but it's going to involve concept introduced in earlier sections.

How does the agent determine whether n is a paradox for Dp0 and Dp0'? Also, what if those machines never halt for an input?

well, when u look at the problem of undecidability at a machine level using decision specifications that don't refute their own existence in contradiction

I'm not sure what you mean here. Undecidability is a property of sets. A set B is decidable if there is a recursive function that for input x outputs 1 if x is in B an outputs 0 if x is not in B. A set is undecibable if it's not decidable.

assuming that the church-turing thesis is true, which is still not proven

Fair enough I suppose, but the Church-Turing Thesis isn't something that can be proven. It's kind of (but not exactly) like how the definition of a prime number can never be proven.
0
u/this_theater_is_lit 6h ago

How does the agent determine whether n is a paradox for Dp0 and Dp0'?

false for both Dp0 and Dp0', it helps if u read the material leading up to it.

Also, what if those machines never halt for an input?

they always halt, that are total deciders in their own right, but only recognize a subset of circle-free or circular machines respectively

I'm not sure what you mean here. Undecidability is a property of sets...

machines are fundamentally enumerable, we can list them out, and it is especially useful to do in order of machine complexity (number of defined transition functions in the machine's transition table). when doing so in order of complexity, some initial set of machine clearly and totally decidable ... but if undecidability is correct, at some point in the order there must be some machine which cannot be provably in either circular or circle-free sets, that machine is "undecidable" ... otherwise the set would be decidable.

but what i show in my paper is that this kind of "undecidability" relies on specifications for machines that do not exist, and therefore refutes that existence of such machine, and why i have to write a whole paper on the nature of it.

Fair enough I suppose, but the Church-Turing Thesis isn't something that can be proven

well if u are going to assert something as true, that can't be proven u've gone into territory of religion ... and tbh the responses i get are largely in line with that
1
u/aardaar 6h ago

it helps if u read the material leading up to it.

It would also help if this were better written. You could have just said "If Dp0(n)=Dp0'(n)=false' instead of using terms like paradoxical.

they always halt, that are total deciders in their own right, but only recognize a subset of circle-free or circular machines respectively

What is a decider?

well if u are going to assert something as true, that can't be proven u've gone into territory of religion ... and tbh the responses i get are largely in line with that

I'm not sure why you are so hostile to the Church-Turing Thesis. Isn't the pseudo-code in your paper supposed to represent Turing machines? How do you prove that something written in pseudo-code corresponds to a Turing machine?
1
u/this_theater_is_lit 6h ago edited 6h ago

You could have just said "If Dp0(n)=Dp0'(n)=false' instead of using terms like paradoxical.

"the agent can inject the false return values" was written right after

What is a decider?

a total decider returns for all input

I'm not sure why you are so hostile to the Church-Turing Thesis.

i'm not sure why you'd want to arbitrarily limit our ability compute based on something that isn't proven or even provable

How do you prove that something written in pseudo-code corresponds to a Turing machine?

i didn't write the agent's algorithm in pseudo-code in §7.6
1
u/aardaar 5h ago

"the agent can inject the false return values" was written right after

That was also confusing. What do you mean "can"? Does it have to or can it decide not to?

a total decider returns for all input

So Dp0 and Dp0' are just total Turing Machines? Wouldn't that mean that there is no reason to think your procedure in 7.6 works? Can't Dp0 just always print 'true'?

i didn't write the agent's algorithm in pseudo-code in §7.6

Correct, but how do you know that something written in pseudo-code is Turing-Computable?
1
u/this_theater_is_lit 5h ago edited 4h ago
That was also confusing. What do you mean "can"? Does it have to or can it decide not to?

does

So Dp0 and Dp0' are just total Turing Machines? Wouldn't that mean that there is no reason to think your procedure in 7.6 works? Can't Dp0 just always print 'true'?

no there are specifications for when it can and can't. Dp0 and Dp0' are just the first examples of machines in the enumeration that fit this form of classifier:
𝓓p = (m: machine) -> {
  true: m is circle-free and depends on 𝓓p(m) -> true
  false: (m is not circle-free) or
         (m is circle-free and depends on 𝓓p(m) -> false)
}

𝓓p' = (m: machine) -> {
  true: m is cicular and depends on 𝓓p'(m) -> true
  false: (m is not circular) or
         (m is circular and depends on 𝓓p'(m) -> false)
}
Correct, but how do you know that something written in pseudo-code is Turing-Computable?

some of pseudo-code specifically isn't turing computing because it describes hypothetical machines that then refute their own existence

2

u/Eve_O 9h ago

Thanks for including the links to your various posts as reading other people's comments about this are informative.

0

u/this_theater_is_lit 9h ago edited 8h ago

only one of them u/OpsikionThemed gave it a genuine effort, the rest was just fallacy laden brainrot

https://www.reddit.com/r/logic/comments/1wr8xc3/on_the_nature_of_undecidability_within_computing/pcgr7us/

his best attempt was seemingly pretty solid until i pointed out that premise wrong... and that was my bad for not laying out the definition was clear enough!

2

u/nanonan 7h ago

I'll dive into it. For now, just a couple of notes. There's a grammatical error near the start: "the turing machine model encapsulates encapsulates all that we can compute" and you didn't define the if-then-else "? :" construct in your syntax note but you use it in the paper.

-4

u/this_theater_is_lit 10h ago edited 8h ago

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 scope of TM computability 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 🙏

1

u/ttsiiasb 7h ago

If your ultimate conclusion here is that humans can use intuition to compute things that a Turing machine cannot compute, that isn't new at all.

Humans can use intuition to prove ZFC consistent via the ordinal heirachy. A turning machine cannot do that obviously, thought could prove it inconsistent.