Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

as you say, the chomsky hierarchy is surely an influence, but i don't think that's the main thing

i think it's probably because a turing machine can do universal computation and can be described completely in a couple of paragraphs, while you need at least several hundred logic gates to describe something that can do universal computation (if you give it infinite memory), and then you still don't have a convincing argument that what it does is universal in any interesting sense

until you bring in turing machines, anyway

you can write a turing machine in about one line of c; the description of a computer in terms of nands doesn't give you that



That seems to be a somewhat strange comparison. Logical circuits are arguably not much more complex than finite-state machines, and theoretical computer science professors don't have an aversion to those. So it doesn't seem like they find logical circuits too primitive. They even seem to strive for primitivity, as Turing machines are much more conceptually primitive than things like register machines or actual CPUs.

Moreover, a logical circuit itself is actually easier to describe than a Turing machine. Both logical circuits with delay and Turing machines can do "universal computation" for any reasonable sense of the term (demanding an infinite element is arguably not reasonable).

And to give a "convincing argument" that they are universal is quite difficult even for Turing machines. What would such an argument even be? In practice, it's more the fact that there are no known counterexamples which causes us to believe in the Church-Turing thesis (that any problem that we would intuitively consider "computable" is also computable with a Turing machine or logical circuit, and vice versa), rather than any one (positive) "convincing argument".


a nand gate is not too primitive, of course, but building an actual cpu out of nand gates involves several hundred of them, and that circuit is harder to describe than a universal turing machine

turing's original paper gave a convincing argument that turing machines were universal; he said that they could do anything a mathematician could do, since the mathematician can only hold a finite number of symbols from a finite set in his memory at once, and can only fit a finite set of symbols from a finite set on a page in his field of view. so the squares on the turing-machine tape were originally pages in a notebook

it seems like you would benefit more from exposing yourself to things you find strange; you could start by reading turing's strange paper https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

strangeness doesn't guarantee insightfulness, but it's a necessary precondition to it; if you continue to dismiss all strange arguments you will dismiss everything from which you could possibly learn anything, preserving your ignorance like a precious jewel


> a nand gate is not too primitive, of course, but building an actual cpu out of nand gates involves several hundred of them, and that circuit is harder to describe than a universal turing machine

Building a CPU with a Turing machine would also be quite complex. Probably less complex, but only because logical circuits are more primitive.

> turing's original paper gave a convincing argument that turing machines were universal; he said that they could do anything a mathematician could do, since the mathematician can only hold a finite number of symbols from a finite set in his memory at once, and can only fit a finite set of symbols from a finite set on a page in his field of view. so the squares on the turing-machine tape were originally pages in a notebook

Yet according to mainstream theoretical computer science (professors), you didn't mention the allegedly relevant property of Turing machines: That the tape is infinitely long. Otherwise it is considered to be equivalent to a mere finite-state machine. Which is, of course, absurd. I think the main difference between FSMs and Turing machines (or logic circuits with delay) is that the latter allow for some sort of "memory", which is (I would guess) a special type of state that finite-state machines don't support.


mostly your comment is wrong from beginning to end

it is important for novices reading this thread to know not to treat it as useful information


You might get more mileage out of Abstract, State Machines. They operate on structures instead of characters. Quite a few tools exist for them, too.


not sure what you mean but i'm glad to hear from you again




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: