4 ms·

I agree. The OP blog post is mistaking. I think the real language misuse is on the behalf of Person A. When asking whether you "can do something in the Foo prog

by p4wnc6 15y ago

I agree. The OP blog post is mistaking. I think the real language misuse is on the behalf of Person A. When asking whether you "can do something in the Foo programming language" this could be a question of theoretical universality or a question of practicality. If it's one of practicality, then it has nothing to do with Turing universality. If it's theoretical, as in "is Foo expressive enough to describe such and such a computation at all", then universality matters. Also, from a computationalist's perspective in Philosophy, Turing completeness literally does mean being able to do anything that a single-taped Turing machine can do (such as writing a GUI or writing to a screen). If you a priori disconnect your Turing machine from the screen, effectively eliminating the logical possibility to print to it (or, similarly, you use some pared down language where specific functionality is intentionally left out) then it makes no sense at all to bring Turing completeness into it. It seems like the OP either rejects the Extended Church Turing thesis, or mistakenly thinks that other people lump all possible hardware limitations into Turing completeness. If a language is resource bounded, then it is only Turing complete w.r.t. a Turing machine that has the same resource bounds.

5hoom 15y ago
Wonderfully put, thank you.
z92 15y ago
Needs paragraph break.
- Despite 15y ago
  I disagree. The paragraphs were comprehensible and held together by subject matter. I had no trouble reading them.
  - p4wnc6 15y ago
    To be fair, originally I had them in one paragraph, then edited them.
andreasvc 15y ago
> anything that a single-taped Turing machine can do (such as writing a GUI or writing to a screen). Wait, those are the things a Turing machine CANNOT do! A Turing machine has no input or output, the computation it defines is purely a function of what's on its tape before and after its work (when it halts). > If you a priori disconnect your Turing machine from the screen Again this makes no sense, the ('a priori') defintion of a Turing machine does not include a screen, so there's nothing to disconnect. It's really just the tape. And no, it's quite a stretch to claim that person A could be talking about universality, the blog post says he was asking about GUIs so that's squarely a practical question. > or [...] thinks that other people lump all possible hardware limitations into Turing completeness. I have no idea how you arrive at this from the blog post.
- p4bl0 15y ago
  OP here. I was going to write just this, I didn't do it until now because I was on my phone and I wanted a real keyboard to answer. So thanks for doing it for me. As a side note, I'll add that "person A"s are people I know IRL and this troll (let's call it what it is) aimed at them, not HN audience ;-).
- ajuc 15y ago
  Turing machine is a tape + some functions that modify this tape. If you connect screen to the tape so it shows part of the content of the tape in some manner - do this mean that Turing machine can print on the screen, or not? Bad analogy: I can write, but I don't have pen and paper bundled from my birth. I understand being able to print to screen as being able to put information in a form that allows screen to show it. Otherways no programming language can print to screen, because programming languages are software, and screen is hardware.
  - p4wnc6 15y ago
    These are just resource limitations. I already addressed that. If you start out with something where a resource limitation prevents you from doing X, then any kind of statement about Turing completeness inherently only draws a comparison with a Turing machine that has the same resource limitation keeping it from doing X. It doesn't matter if this is sending RGB data to a monitor (which some languages cannot do unless augmented with certain hardware) or computing Kolmogorov complexity (which no language can do in general). A human plus paper and pencil is a different computation than a human without paper and pencil, just in terms of hardware and memory. It also seems like some of you are not computationalists. Anything physical is just the result of a computation, whether you are talking about the chemistry of producing colors on a monitor or adding two numbers by sending electrons through circuits of transistors. The ECT thesis says that anything which can be computed in the real world can be computed efficiently by some Turing machine. This includes anything a brain can do (aided by pen and paper or unaided) and certainly includes anything your graphics driver can do. If Java can't do something that Java + Graphics Card + OS can do, then Java has a more serious resource bound, and all claims of Java's Turing completeness inherently include this resource bound. You guys might like some sections of this research paper: (http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf).

by p4wnc6 15y ago

5hoom 15y ago

Wonderfully put, thank you.

z92 15y ago

Needs paragraph break.

Despite 15y ago
I disagree. The paragraphs were comprehensible and held together by subject matter. I had no trouble reading them.
- p4wnc6 15y ago
  To be fair, originally I had them in one paragraph, then edited them.

andreasvc 15y ago

> anything that a single-taped Turing machine can do (such as writing a GUI or writing to a screen). Wait, those are the things a Turing machine CANNOT do! A Turing machine has no input or output, the computation it defines is purely a function of what's on its tape before and after its work (when it halts). > If you a priori disconnect your Turing machine from the screen Again this makes no sense, the ('a priori') defintion of a Turing machine does not include a screen, so there's nothing to disconnect. It's really just the tape. And no, it's quite a stretch to claim that person A could be talking about universality, the blog post says he was asking about GUIs so that's squarely a practical question. > or [...] thinks that other people lump all possible hardware limitations into Turing completeness. I have no idea how you arrive at this from the blog post.

p4bl0 15y ago
OP here. I was going to write just this, I didn't do it until now because I was on my phone and I wanted a real keyboard to answer. So thanks for doing it for me. As a side note, I'll add that "person A"s are people I know IRL and this troll (let's call it what it is) aimed at them, not HN audience ;-).
ajuc 15y ago
Turing machine is a tape + some functions that modify this tape. If you connect screen to the tape so it shows part of the content of the tape in some manner - do this mean that Turing machine can print on the screen, or not? Bad analogy: I can write, but I don't have pen and paper bundled from my birth. I understand being able to print to screen as being able to put information in a form that allows screen to show it. Otherways no programming language can print to screen, because programming languages are software, and screen is hardware.
- p4wnc6 15y ago
  These are just resource limitations. I already addressed that. If you start out with something where a resource limitation prevents you from doing X, then any kind of statement about Turing completeness inherently only draws a comparison with a Turing machine that has the same resource limitation keeping it from doing X. It doesn't matter if this is sending RGB data to a monitor (which some languages cannot do unless augmented with certain hardware) or computing Kolmogorov complexity (which no language can do in general). A human plus paper and pencil is a different computation than a human without paper and pencil, just in terms of hardware and memory. It also seems like some of you are not computationalists. Anything physical is just the result of a computation, whether you are talking about the chemistry of producing colors on a monitor or adding two numbers by sending electrons through circuits of transistors. The ECT thesis says that anything which can be computed in the real world can be computed efficiently by some Turing machine. This includes anything a brain can do (aided by pen and paper or unaided) and certainly includes anything your graphics driver can do. If Java can't do something that Java + Graphics Card + OS can do, then Java has a more serious resource bound, and all claims of Java's Turing completeness inherently include this resource bound. You guys might like some sections of this research paper: (http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf).