4 ms·
That seems to be a somewhat strange comparison. Logical circuits are arguably not much more complex than finite-state machines, and theoretical computer science
by cubefox 3y ago
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".
- kragen 3y agoa 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 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
- cubefox 3y ago> 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.