5 ms·
If you assume that halt does exist to make your solution valid, then you can derive any statement (including that addition does not exist), because that assumpt
by Gehinnn 4y ago
If you assume that halt does exist to make your solution valid, then you can derive any statement (including that addition does not exist), because that assumption is false.
In general:
Let P be a statement. Lets assume that the Turing Machine T solves the halting problem - let's call this assumption H.
Now we assume P is false. Now we have a contradiction - H says that T solves the halting problem, but we know that there is not Turing machine that can solve the halting problem!
Thus P must be true!
Notice that P is arbitrary.
Plainly speaking:
If you assume that the halting problem can be solved, I can formally prove you that addition does not exist (i.e. there is no operation +, such that it forms a group on Z)
> By the logic (as written) of the article the implication is that '+' does not exist.
This is actually true. With that strong assumption, + does not exist.
- constantcrying 4y agoI am at a total loss here. Do you not understand that it is the point that my reasoning is invalid? Why are you pretending I do not understand the basics of logic while missing the actual argument by a mile?
- Gehinnn 4y agoYour reasoning is valid, and I do have the impression that you should refresh your knowledge about logic.
- constantcrying 4y agoAs a reminder: a proof by contradiction works by assuming first the negation of a given statement. If from that you can deduce a falsehood you know that statement is true. In the article the author says: "If you implement halts using canBeRegex, you’ve got a proof by contradiction that canBeRegex can’t exist." Which is plainly a false statement. What he means is the following statement: "If you show that if canBeRegex is computable then halts is computable, you’ve got a proof by contradiction that canBeRegex can’t exist." Those two statements are clearly not equivalent. And only the second one is true.
- dellamonica 4y agoWait, so you are saying that the only thing missing in the first statement is that the implementation is required to be correct? I think that is pretty obvious. This is beyond nitpicking.
- constantcrying 4y ago>that the implementation is required to be correct? No. "Implemented" is in fact irrelevant, it is clearly not the term to use here. Because what the implementation uses is irrelevant, the question is about whether computability in one can be derived from computability of the other. In his example the implementation also uses ".length", whether it does or doesn't is irrelevant though. Since it is not a question of implementation. >This is beyond nitpicking. Also known as standard practice in mathematics.
- dellamonica 4y agoImplemented in this context means exactly the type of reduction that is needed. If halt can be implemented by using X that means you can reduce X to halt. This is similar to polynomial time reductions in complexity. Standard practice in mathematics would apply here if what was said is wrong. This time it is about an interpretation that no one shares with you. [edit] After reading again your comment I realized that maybe you are not applying the logic correctly. If the reduction "implementation" uses both length and foo, then the conclusion is that at least one of length or foo cannot be computable. Since length is trivial, then it must be foo that is not computable.
- constantcrying 4y ago>If halt can be implemented by using X that means you can reduce X to halt. Replace X with .length and read your statement again. "If halt can be implemented by using .length that means you can reduce .length to halt." Please just answer whether you believe that statement is true or false (or undecidable).