"andrel" <a_l### [at] hotmailcom> wrote in message
news:4A6### [at] hotmailcom...
> On 22-7-2009 20:30, somebody wrote:
> > "Warp" <war### [at] tagpovrayorg> wrote in message
> > news:4a671eb6@news.povray.org...
> >> Invisible <voi### [at] devnull> wrote:
> >
> >>> It's common knowledge that if you write an arbitrary program in a
> >>> Turing-complete programming language, it is impossible to determine
> >>> whether the program will ever halt.
> >
> >>   That's not stated correctly. It's impossible to create an algorithm
> > which
> >> would tell for all possible programs whether they terminate or not.
> >
> > Even so, one has to be careful, for it's possible to determine if any
such
> > finite program will halt or not - just run the program until all
possible
> > states would be exhausted.

> Why would the number of states be finite and why do you assume
determinism?

The Turing process does not prescribe for true randomness. And with
determinism plus finite resources, states will be finite.

Post a reply to this message