4 ms·

This is not false. If you can implement halt using addition, addition cannot exist. Ex falso quod libet - if you can prove a single false statement, every sta

This is not false. If you can implement halt using addition, addition cannot exist. Ex falso quod libet - if you can prove a single false statement, every statement is true.

constantcrying 4y ago
Here is a solution of the halting problem which is implemented using addition: function haltWithAdd(code) { var a = 1 + 2; return halt(code); } This clearly solves the halting problem (we assumed the existence of halt as the first step of our proof by contradiction). And it clearly uses addition (surely you can find where it does). By the logic (as written) of the article the implication is that '+' does not exist.
- akdas 4y ago
  > This clearly solves the halting problem (we assumed the existence of halt as the first step of our proof by contradiction). Implementing the halting problem using addition does not assume the existence of halt. It assumes the existence of addition, and you use that to show that halt must also exist. And that's not possible to do. To implement halts using addition, you need to: - Take the input to halts, namely the source code to a program. - Convert that into an input to addition, namely two numbers. - Call into addition, which adds the numbers. - Use the result of that addition to infer whether the original program halts or not.
  - constantcrying 4y ago
    Why are you debating the validity of the argument? The code very clearly: - is an implementation of the halting problem. If halt existed it would undoubtly solve the halting problem - it uses '+' You are prentending I didn't know what the author meant. The point is that what the author says is simply not true, if you take the statement as written. What he wants to show is that if canBeRegex is computable then halt is computable, but that isn't what he is saying.
- gweinberg 4y ago
  You're not getting it. A "CanBeRegex" function which (always) correctly indicates whether a code block could be replaced by a regex MUST be able to solve the halting problem. The same is not true for addition.
  - constantcrying 4y ago
    You are not getting it. What you are saying is not what the author says. I know what the author wants to say, but it isn't what he actually says.
- 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 ago
    I 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 ago
      Your reasoning is valid, and I do have the impression that you should refresh your knowledge about logic.
      - constantcrying 4y ago
        As 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.
tromp 4y ago
The author uses "implement halts using X" in the sense of reducing the halting problem to the problem of X (technically, using Turing reduction). Not in the sense of solving the halting problem with a function which has an occurrence of X.
- Gehinnn 4y ago
  Why would this distinction matter for the argument?
  - dellamonica 4y ago
    It does not matter at a high level but I think the distinction is that there should be only one black box in the proof, which is precisely the thing being reduced. Every other instruction/call used n the algorithm must be known to be computable (in this case, addition).

This is not false. If you can implement halt using addition, addition cannot exist. Ex falso quod libet - if you can prove a single false statement, every statement is true.

constantcrying 4y ago

Here is a solution of the halting problem which is implemented using addition: function haltWithAdd(code) { var a = 1 + 2; return halt(code); } This clearly solves the halting problem (we assumed the existence of halt as the first step of our proof by contradiction). And it clearly uses addition (surely you can find where it does). By the logic (as written) of the article the implication is that '+' does not exist.

akdas 4y ago
> This clearly solves the halting problem (we assumed the existence of halt as the first step of our proof by contradiction). Implementing the halting problem using addition does not assume the existence of halt. It assumes the existence of addition, and you use that to show that halt must also exist. And that's not possible to do. To implement halts using addition, you need to: - Take the input to halts, namely the source code to a program. - Convert that into an input to addition, namely two numbers. - Call into addition, which adds the numbers. - Use the result of that addition to infer whether the original program halts or not.
- constantcrying 4y ago
  Why are you debating the validity of the argument? The code very clearly: - is an implementation of the halting problem. If halt existed it would undoubtly solve the halting problem - it uses '+' You are prentending I didn't know what the author meant. The point is that what the author says is simply not true, if you take the statement as written. What he wants to show is that if canBeRegex is computable then halt is computable, but that isn't what he is saying.
gweinberg 4y ago
You're not getting it. A "CanBeRegex" function which (always) correctly indicates whether a code block could be replaced by a regex MUST be able to solve the halting problem. The same is not true for addition.
- constantcrying 4y ago
  You are not getting it. What you are saying is not what the author says. I know what the author wants to say, but it isn't what he actually says.
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 ago
  I 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 ago
    Your reasoning is valid, and I do have the impression that you should refresh your knowledge about logic.
    - constantcrying 4y ago
      As 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.

tromp 4y ago

The author uses "implement halts using X" in the sense of reducing the halting problem to the problem of X (technically, using Turing reduction). Not in the sense of solving the halting problem with a function which has an occurrence of X.

Gehinnn 4y ago
Why would this distinction matter for the argument?
- dellamonica 4y ago
  It does not matter at a high level but I think the distinction is that there should be only one black box in the proof, which is precisely the thing being reduced. Every other instruction/call used n the algorithm must be known to be computable (in this case, addition).