On 2024-01-19 22:50:34 +0000, Alan Mackenzie said:
In comp.theory Richard Damon <[email protected]> wrote:
[ .... ]
Only a simulation that shows that you can not reach a final state even
after an unbounded number of steps shows non-halting, but doing such a
simulation make the machine fail to be a decider, as deciders must
answer in bounded time, and until you invent a time machine, you can't
do unbounded work in bounded time.
Is that right? Deciders must answer in finite time, but is there
actually a bound on how long this time can be? If so, what is it?
Both the decider and every possible input to the decider can be
described with a finite string. There are only a finite number of
program-input pairs that can be described with a string of the same
length or shorter. Each of those pairs represent a halting or
non-halting computation. Each of the halting computation has a
computation time, and because the number of those computations
is finite, there is a maximum time that is the time of one or more
of those computations. Considering all descriptions of program-input
pairs of any length, for each length there is a maximum time that
is only exceeded by non-halting programs. However, there is no
way to compute that time from the length.
Mikko
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)