3 ms·

> But arguably, logical gates are much more conceptually primitive than most of those automata above! They are basically an implementation of propositional logi

> But arguably, logical gates are much more conceptually primitive than most of those automata above! They are basically an implementation of propositional logic, albeit potentially with a dimension of time and delay. And they are nonetheless somewhat close to how actual computers work. So why do they ignore them as a model of computation? Simple: logic circuits for propositional logic are not Turing-complete, and in a lecture about theoretical computer science one wants to teach such more sophisticated, mathematical models of computation. On the other hand, in basically every beginner lecture about computer engineering (in German: "technische Informatik"), they will teach you how how the transition function of a finite-state machine can be implemented via combinational logic (https://en.wikipedia.org/wiki/Combinational_logic https://en.wikipedia.org/wiki/Combinational_logic), which can be transformed into logic gates for implementing a Mealy machine (https://en.wikipedia.org/wiki/Mealy_machine https://en.wikipedia.org/wiki/Mealy_machine) or Moore machine (https://en.wikipedia.org/wiki/Moore_machine https://en.wikipedia.org/wiki/Moore_machine) in hardware.

cubefox 3y ago
> Simple: logic circuits for propositional logic are not Turing-complete, and in a lecture about theoretical computer science one wants to teach such more sophisticated, mathematical models of computation. Logical circuits with delay (sequential [1] rather than combinational logic) are indeed not Turing complete -- but in the same uninteresting sense that a CPU is not Turing complete: In a conceptually irrelevant way. As I argued, Turing machines are precisely not "much more sophisticated" than CPUs or the circuits they are made out of. Turing machines merely have infinite rather than potentially infinite memory. You could modify the concept of a Turing machine such that its tape is potentially rather than actually infinite, and it would change nothing of substance. Yet this machine would suddenly only be considered equivalent to a finite-state machine. Apart from that, a perhaps theoretically interesting point about combinational logic (circuits without time/delay) and finite state machines would be that combinational logic is apparently computationally weaker than finite-state machines. Wikipedia doesn't say anything about that explicitly, but the "classes of automata" image [2] they include in the article does suggest it. But that, assuming it's true, should be taught in theoretical computer science class, not in computer engineering (if the latter mentions it at all). But, much more importantly, they -- the theoretical computer science professors, not the engineering guys -- should explain the theoretical relation between circuits with delay (sequential logic) and various automata, including Turing machines. The likely fact is that they ignore circuits because they don't fit well into their supposedly neat picture of abstract machines. In fact, they call their reliance on infinity as an important difference between models of computation in question. [1] https://en.wikipedia.org/wiki/Sequential_logic https://en.wikipedia.org/wiki/Sequential_logic [2] https://en.wikipedia.org/wiki/File:Automata_theory.svg https://en.wikipedia.org/wiki/File:Automata_theory.svg

cubefox 3y ago

> Simple: logic circuits for propositional logic are not Turing-complete, and in a lecture about theoretical computer science one wants to teach such more sophisticated, mathematical models of computation. Logical circuits with delay (sequential [1] rather than combinational logic) are indeed not Turing complete -- but in the same uninteresting sense that a CPU is not Turing complete: In a conceptually irrelevant way. As I argued, Turing machines are precisely not "much more sophisticated" than CPUs or the circuits they are made out of. Turing machines merely have infinite rather than potentially infinite memory. You could modify the concept of a Turing machine such that its tape is potentially rather than actually infinite, and it would change nothing of substance. Yet this machine would suddenly only be considered equivalent to a finite-state machine. Apart from that, a perhaps theoretically interesting point about combinational logic (circuits without time/delay) and finite state machines would be that combinational logic is apparently computationally weaker than finite-state machines. Wikipedia doesn't say anything about that explicitly, but the "classes of automata" image [2] they include in the article does suggest it. But that, assuming it's true, should be taught in theoretical computer science class, not in computer engineering (if the latter mentions it at all). But, much more importantly, they -- the theoretical computer science professors, not the engineering guys -- should explain the theoretical relation between circuits with delay (sequential logic) and various automata, including Turing machines. The likely fact is that they ignore circuits because they don't fit well into their supposedly neat picture of abstract machines. In fact, they call their reliance on infinity as an important difference between models of computation in question. [1] https://en.wikipedia.org/wiki/Sequential_logic https://en.wikipedia.org/wiki/Sequential_logic [2] https://en.wikipedia.org/wiki/File:Automata_theory.svg https://en.wikipedia.org/wiki/File:Automata_theory.svg