Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

>Anything that can recurse or fall into an infinite loop is Turing complete.

My computer can fall into an infinite loop even though it doesn't have infinite storage (to emulate an infinite tape of a Turing machine).



No it can’t because there isn’t infinite energy.


I never said that my computer would run forever. I simply stated that it would fall into an infinite loop. You could argue that cosmic rays could cause a bit flip to get the computer out of an infinite loop, but that it is out of scope.


Does the program halt when the power cuts out?

I think our disagreement is specious because it’s trying to import terms like “infinite loop”, “halt”, “program” from a formal theory into the material world.

I think I can only ask, how do you define infinite loop and forever?


>Does the program halt when the power cuts out?

Yes. A computer can be in an infinite loop, lose power, and then stop functioning.

>how do you define infinite loop and forever

Infinite Loop: A system is in an infinite loop when that system keeps returning to the same state making it unable to progress (depending on the context the definition might change to where making progress is okay and it in only returning to a partial match of an existing state (think of an echo server for example))

Forever: A time period that ranges from t=now to t=infinity.


> Yes. A computer can be in an infinite loop, lose power, and then stop functioning.

Ok. Are these claims accurate?

1. All physical systems must eventually halt.

2. In many cases physical systems correspond to formal computational systems.

> Infinite Loop: A system is in an infinite loop when that system keeps returning to the same state making it unable to progress

A system is called deterministic if all future states can be calculated from complete knowledge of any particular state.

So then because the system is deterministic, we know that if it returns to a previous state it must keep returning to this state forever?

> Forever: A time period that ranges from t=now to t=infinity.

Right, it’s a period of time, but the word “infinity” is not clarifying for me. Maybe, a period of time with no end?


>1. All physical systems must eventually halt.

In terms of physical computers I don't agree with must, but I will say there is a very high chance that it will. In terms of an arbitrary physical system something like gravity doesn't just halt.

>In many cases physical systems correspond to formal computational systems.

It is possible to model physical systems. It can also be useful to reason about a simplified model of something.

>So then because the system is deterministic, we know that if it returns to a previous state it must keep returning to this state forever?

Assuming it's deterministic then yes. Depending on how complicated your model is it may be hard to go back to a state you were in before.

>Maybe, a period of time with no end?

Sure.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: