Menu
I've studied the basic turing machine theory as an undergraduate. I never saw any mention of a timed turing maching. An example: a turing machine that counts the number of seconds passed since it started.
Modern computers clearly have the capacity to do this. So, a computer's capability is a superset of what a turing machine can do. Are there some articles/math/documentation on this? Or is my argument wrong at some point?
586
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm.
The time complexity of a TM M is a function (typically denoted f(n)) that measures the worst-case number of steps M takes on any input of length n. By convention, n denotes the length of the input. If M loops on some input of length k, then f(k) = ∞. The previous TM has time complexity f(n) = n + 1.
Turing machines are similar to finite automata/finite state machines but have the advantage of unlimited memory. They are capable of simulating common computers; a problem that a common computer can solve (given enough memory) will also be solvable using a Turing machine, and vice versa.
Turing machine doesnt use time because it doesnt need to, it's a purely computational device, and computation is not derivation of time, but the time is derivation of computation. Still, it's a mechanical device, so because of that it takes time to make steps, so the machine can potentially count this time too, but that would require another truing machine to do it.
ps. It's because of the entropy, the time is derived from computation. You can reset computer in no-time, - this is in the opposite direction of entropy. So that's why booting almost always takes longer than shutting down, especially if you disconnect the power.
171
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
