3 ms·

> 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 T

> 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).
galactus 15y ago
Strictly speaking no GUI can be written using only a programming language like perl, java, tcl... I/O has nothing to do in the discussion comparing Turing Complete vs. "supporting some language feature in a way that makes it practical for humans to use it.".
- p4wnc6 15y ago
  What is a programming language other than a language for creating instructions for moving pieces of matter around? You could do this with Java if you give it the same physical resources that the current graphics pipelines have. That stuff isn't exposed to Java and would be pretty cumbersome to manipulate with Java, but it can still in principle be done.

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).

galactus 15y ago

Strictly speaking no GUI can be written using only a programming language like perl, java, tcl... I/O has nothing to do in the discussion comparing Turing Complete vs. "supporting some language feature in a way that makes it practical for humans to use it.".

p4wnc6 15y ago
What is a programming language other than a language for creating instructions for moving pieces of matter around? You could do this with Java if you give it the same physical resources that the current graphics pipelines have. That stuff isn't exposed to Java and would be pretty cumbersome to manipulate with Java, but it can still in principle be done.