Hacker News Reader

Comment by cleverjake | Hacker News Reader

While I agree that it is a bit of a misnomer to say that anything is possible in a turing complete language from a feasibility stand point, I think this response falls back to a common thought process that technical minded people go through - literal answers. Of course it is possible to do it, it may just be incredibly difficult. When most people ask if they can do X in Foo, they are usually asking if it is a good idea to do X in Foo. Should the person being asked tell them no even if it is a possibility that is not easy?

View on HN

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.

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

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.

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

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

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.

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

Needs paragraph break.

I disagree. The paragraphs were comprehensible and held together by subject matter. I had no trouble reading them.

To be fair, originally I had them in one paragraph, then edited them.

Wonderfully put, thank you.

Agreed (also agree with another post at this level).

It seems like a clever "nit" to pick but the only thing you need to add to "turing complete" is "able to address memory in a reasonable way" (or "not sandboxed from memory") and you get everything the author is complaining about and you're back to square one (i.e. the language is "turing complete and has memory access".

How do I print? I stick stuff in the right places in memory and set the program counter. How do I draw graphics? I stick stuff in the right place in memory and set the program counter.

I think it's also due to some people kinda-sorta understanding what Turing Completeness means, and then applying it to everything to sound smart.

Reply on news.ycombinator.com