質問

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?

役に立ちましたか?

解決

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.

他のヒント

Of course Turing machine can compute time.

Let's say your Turing machine makes a step each second.

  1. Write current time on the tape of Turing machine (equals setting time in BIOS or downloading it from internet)

  2. Edit the machine, so it adds 1 secont to the time on tape in each step (equals electric "tick generator" on motherboard increases the number in BIOS in each tick)

Now you can put this turing machine on the wall. You will see the exact time every time you look at it's tape.

But remember, Turing machine works with an alphabet. Computers work with alphabet {0,1}. Turing machine (or computer) does not know, whether these zeros and ones represent letters, numbers, pictures or videos.

You might want to read the informal definition or, if you prefer, the formal defintion of what a turing machine is on Wikipedia

Randomly googling I also found this which seems to be promising.

I think in short, you are right, computers are more convenient than turing machines but basically no device can ever solve something which isn't solvable with one or more turing machines.

ライセンス: CC-BY-SA帰属
所属していません StackOverflow
scroll top