Hacker News new | ask | show | jobs
by stellaathena 1590 days ago
I/O is covered by Turing completeness. Whether timing is depends significantly on how exactly you want to formalize things, but certainly any TC system has the capacity to keep track of time if the pieces are manipulated at a constant rate.
3 comments

> I/O is covered by Turing completeness.

Not really. A plain turing machine only has one input and one output over the lifetime of the execution.

> certainly any TC system has the capacity to keep track of time if the pieces are manipulated at a constant rate.

Only if the turing-equivalent machine is iterating at a specific rate and can pause. Lots of these systems run through the entire machine in a single shot and can't manage timing.

It's not so much keeping track of time, but that that time matches the real world outside the machine. The whole Tetris Complete formalization is about how a given machine (which as a previous comment points out, doesn't need to be turing complete) relates to the non-theoretical non-computational world. Turing completeness requires or even suggests any of those things, it's an orthogonal concept.
What IO capabilities does the lambda calculus have?