4 ms·

This is an interesting article, but I'm still fairly confused about the notion that is made >Harper’s attack on the utility of machine models and lack of modul

by LolWolf 10y ago

This is an interesting article, but I'm still fairly confused about the notion that is made >Harper’s attack on the utility of machine models and lack of modularity is tantamount to an architect saying to a chemist, “both of our disciplines concern the arrangement of molecules, yet my discipline is superior, as yours doesn’t even have the modular notion of a room!” But wouldn't the whole point be that a chemist, seeing the room as nothing less than an abstraction, can also understand the room through their given framework? Much in the same way that, for any computational model, we can think of a TM with an Oracle tape, or some similar IO model, that has the same computational power as any defined language? I'm afraid that I thought I understood the distinction at first: where those who support CT view computation as a fundamental case (e.g. every other mathematical 'primitive' can be derived from a computation with the appropriate oracles[1]) and and the TOP view which sees mathematical foundations as the main case, and then sees computers as being an abstraction of functions in some sense, such that one can construct a calculus of these functions which constitutes a language. Did I get this all wrong? I'm afraid I still don't understand the main distinction to be honest. It seems that both parties are going around in circles on exactly the same thing, but assuming different axiomatic systems and showing that each is equivalent to the other. [1] For example, with no oracles, we receive all of constructive mathematics, etc.

pron 10y ago
You can translate and transform many things to many others. The important question is what is the computational complexity of the transformation? If it is large, then the two things are very different. As Scott Aaronson once said, waterfalls could be viewed as playing chess, but as the complexity of the translation from the "waterfall language" to a chess language understandable by humans is as great as the complexity of an actual chess-playing program, all the work is done in the translation. So the question you should be asking is where the complexity is being spent and on what.
- LolWolf 10y ago
  Wait, but I thought the question being posed wasn't about the computational complexity of any model but about the power of a given computational model relative to another (e.g. the subject of the CT thesis). Even if we're talking about just computational complexity, if we allow Turing machines with arbitrary oracles, or (equivalently) we allow arbitrary mathematical constructions in languages, I'm still unsure as to why the complexity matters. W.r.t the waterfall case. Sure, I agree with that statement, but I'm unsure as to how it plays into the final case---the question isn't about a specific model performing a specific task, but about a model being able to completely replicate another in terms of computational power. Anything I can do in a language (with some functions) I can do in a Turing machine with the appropriate oracles; and conversely, anything I can do in a Turing machine with some given oracles, I can do in a language.
  - marcosdumay 10y ago
    What I get is that the question is "Does it make any sense to compare the two models, or are they just different things?" and the tentative answer is "They are different things, but one end of TOP coincides with TOC". I'm fully convinced. Both concepts answer different questions, and that is my favorite test (instead of the OP's "does one model map into the other?").
  - pron 10y ago
    Both models are equally powerful in the things they compute in terms of the Church-Turing Thesis. The TOP view also has other consideration. My point in the article was not to settle the debate on Aaronson's blog but to show that language models and machine models are objectively and inherently so different from one another that comparing them in terms of programming concepts (like types) is meaningless.
    - LolWolf 10y ago
      I see, okay; I caught that point in the article through the first part, but the latter part got me stuck back on the same point hence the question. Thank you for the clarification.
    - AnimalMuppet 10y ago
      And it seems that most of the "my way is superior to yours" is based on setting up strawmen of "yours" to make it be addressing the same questions as "mine".
      - pron 10y ago
        Yes, but it goes a little further. I can't say my way is superior to yours if my way means solving a harder task and paying market price for it. I got the leather seats because I chose to pay full price for them. That they come as a standard option with the car because the car is more expensive is not an argument. You can choose to pay the same difference in price and have them installed in your car, too. Whether those leather seats matter or not is no longer an objective question but a question of values, and here is where caring about completely different values is the point.
- clusmore 10y ago
  >The important question is what is the computational complexity of the transformation? In my view it makes no sense to use metrics from one model on the other. There is no computational complexity involved in the transformations defined in ToP. This is like measuring the computational complexity of a mathematical proof - it has no complexity, it's delcarative.
  - deleted 10y ago
    [deleted]
  - pron 10y ago
    > This is like measuring the computational complexity of a mathematical proof - it has no complexity, it's delcarative. There are few things that are absolute in this universe, but computational complexity is one of them. There is plenty of complexity involved. Have your heard of proof complexity? How do you know that a proof is a proof and how is a proof created? It's pretty much the core of P vs. NP question (and first discussed by Stephen Cook, the same guy who formally framed P vs. NP): https://en.wikipedia.org/wiki/Proof_complexity https://en.wikipedia.org/wiki/Proof_complexity Actually, the first one who asked the question of P vs. NP was Kurt Gödel (https://rjlipton.wordpress.com/the-gdel-letter/ https://rjlipton.wordpress.com/the-gdel-letter/), and as a mathematician, he was very much interested in the complexity (although he didn't use that word) of proofs. He said that if P = NP (not in those words): > If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n2), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine.

by LolWolf 10y ago

pron 10y ago

You can translate and transform many things to many others. The important question is what is the computational complexity of the transformation? If it is large, then the two things are very different. As Scott Aaronson once said, waterfalls could be viewed as playing chess, but as the complexity of the translation from the "waterfall language" to a chess language understandable by humans is as great as the complexity of an actual chess-playing program, all the work is done in the translation. So the question you should be asking is where the complexity is being spent and on what.

LolWolf 10y ago
Wait, but I thought the question being posed wasn't about the computational complexity of any model but about the power of a given computational model relative to another (e.g. the subject of the CT thesis). Even if we're talking about just computational complexity, if we allow Turing machines with arbitrary oracles, or (equivalently) we allow arbitrary mathematical constructions in languages, I'm still unsure as to why the complexity matters. W.r.t the waterfall case. Sure, I agree with that statement, but I'm unsure as to how it plays into the final case---the question isn't about a specific model performing a specific task, but about a model being able to completely replicate another in terms of computational power. Anything I can do in a language (with some functions) I can do in a Turing machine with the appropriate oracles; and conversely, anything I can do in a Turing machine with some given oracles, I can do in a language.
- marcosdumay 10y ago
  What I get is that the question is "Does it make any sense to compare the two models, or are they just different things?" and the tentative answer is "They are different things, but one end of TOP coincides with TOC". I'm fully convinced. Both concepts answer different questions, and that is my favorite test (instead of the OP's "does one model map into the other?").
- pron 10y ago
  Both models are equally powerful in the things they compute in terms of the Church-Turing Thesis. The TOP view also has other consideration. My point in the article was not to settle the debate on Aaronson's blog but to show that language models and machine models are objectively and inherently so different from one another that comparing them in terms of programming concepts (like types) is meaningless.
  - LolWolf 10y ago
    I see, okay; I caught that point in the article through the first part, but the latter part got me stuck back on the same point hence the question. Thank you for the clarification.
  - AnimalMuppet 10y ago
    And it seems that most of the "my way is superior to yours" is based on setting up strawmen of "yours" to make it be addressing the same questions as "mine".
    - pron 10y ago
      Yes, but it goes a little further. I can't say my way is superior to yours if my way means solving a harder task and paying market price for it. I got the leather seats because I chose to pay full price for them. That they come as a standard option with the car because the car is more expensive is not an argument. You can choose to pay the same difference in price and have them installed in your car, too. Whether those leather seats matter or not is no longer an objective question but a question of values, and here is where caring about completely different values is the point.
clusmore 10y ago
>The important question is what is the computational complexity of the transformation? In my view it makes no sense to use metrics from one model on the other. There is no computational complexity involved in the transformations defined in ToP. This is like measuring the computational complexity of a mathematical proof - it has no complexity, it's delcarative.
- deleted 10y ago
  [deleted]
- pron 10y ago
  > This is like measuring the computational complexity of a mathematical proof - it has no complexity, it's delcarative. There are few things that are absolute in this universe, but computational complexity is one of them. There is plenty of complexity involved. Have your heard of proof complexity? How do you know that a proof is a proof and how is a proof created? It's pretty much the core of P vs. NP question (and first discussed by Stephen Cook, the same guy who formally framed P vs. NP): https://en.wikipedia.org/wiki/Proof_complexity https://en.wikipedia.org/wiki/Proof_complexity Actually, the first one who asked the question of P vs. NP was Kurt Gödel (https://rjlipton.wordpress.com/the-gdel-letter/ https://rjlipton.wordpress.com/the-gdel-letter/), and as a mathematician, he was very much interested in the complexity (although he didn't use that word) of proofs. He said that if P = NP (not in those words): > If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n2), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine.