News for hackers. Stuff that matters.
Re:Accidentally Turing-Complete by charcircuit on Saturday February 05, 2022 @06:13AM (#30220044)
>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).

Re:Accidentally Turing-Complete by burrows on Saturday February 05, 2022 @06:40AM (#30220161)
No it can’t because there isn’t infinite energy.
Re:Accidentally Turing-Complete by charcircuit on Saturday February 05, 2022 @06:51AM (#30220225)
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.
Re:Accidentally Turing-Complete by burrows on Saturday February 05, 2022 @07:38AM (#30220442)
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?

Re:Accidentally Turing-Complete by charcircuit on Saturday February 05, 2022 @08:03AM (#30220594)
>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.

Re:Accidentally Turing-Complete by burrows on Saturday February 05, 2022 @08:30AM (#30220790)
> 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?

Re:Accidentally Turing-Complete by charcircuit on Saturday February 05, 2022 @09:16AM (#30221177)
>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.