🚀 go-pugleaf

stephen@pesto.uchicago.edu (Stephen P Spackman) writes:

>I think the observation here is that actual computers are NOT
>(equivalent to) turing machines BECAUSE they have finite resources.
>Note that it doesn't matter WHAT the bound on resources is; so long as
>it is there, and has some value in each case, the theoretical
>observation that this is NOT REALLY a turing machine holds.

This is true in a theoretical sense, but in practical terms, it really
doesn't make that much of a difference.  Remember the number of possible
states grows exponentially!

>So the question is, *can we get any mileage out of that*? What useful
>theorems could we prove if we were to grant (or assume, if it makes
>you feel better - maybe your computer is A LOT bigger than mine :-)
>that there IS SOME upper bound on machine state complexity?

>Now, I don't do theory, and I haven't spent a lot of time worrying
>about the structure of the appropriate theorems (though it does seem
>pretty obvious that a FINITE computer has an easy check for programme
>termination: wait until it has run enough cycles to be in EVERY state.
>By this point it has either halted or it is in an infinite loop, by
>a pigeonhole argument.

Nice idea, but you've missed something fundamental.  A turing machine
consists of a state machine AND its "tape".  You need to account for the
initial state of the tape as well.  You could have a two state FSM (one is the
halted state) which will run, not in an infinite loop, but as long as the
tape "tells" it to.  The only "easy" cases I know of are:  No halted state,
and no loops.  Anything else can get really hard, really fast.  Assuming that
there IS an answer, which is not always the case.

>                       It's not PRACTICAL, of course, but that
>doesn't mean it has no practical CONSEQUENCES); but it doesn't seem at
>all incoherent that it MIGHT be very important.

>And it certainly means there's room for different perspectives on
>what's "possible".

Indeed.
--
T.T.F.N.,
dave truesdell (truesdel@nas.nasa.gov)
'And Ritchie said, "Let there be portability!"  And nothing happened, so
 Ritchie realized that he had his work cut out for him.'