Does a turing machine have the concept of 'time'?

Question

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?

Vinegarette

Answer 1

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.

Baese

Hmm - that would mean you're using two turing machines. But if you can do it with two turing machines, you should be able to do it with just one. – Vinegarette

Well I thought that it would need some reference to calculate this time, and for this can be a turing machine making step every second with no condition, and updating the counter. The other machine cannot do step every second, because it works e.g. every 1/3s, so it cant measure itself. In fact, it wont even tell when it will hang, so the other machine would be measuring time and when it stops. – Baese

ps. The major problem with turing machine is that it's using concept of infinite tape length. The problem is that it's only a theory. Same as one would assume infinite speed of light. In practice, it's only conceptual model which is incomplete from practical point of view. So if the tape would finish on the 1-st one, it would not print this time, and it would fail like with BSOD, and to have a value of this, you would require another machine. – Baese

Answer 2

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.

Malik

How does the turning machine know exactly one second has passed? – Vinegarette

What do you mean by "know" ? I slightly edited my comment.Computer does not "know" anything. It just has some "state" (data) in it's memory (tape). – Malik

Answer 3

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.

Scherzo

... or by a cluster of turing machines. – Baese