Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Scooping the Loop Snooper (2000)

lel.ed.ac.uk

Post reply on HN
Print view View original

21–30 of 34 posts

Re: Scooping the Loop Snooper (2000)

#21

Post by andreareina »

Animats wrote: post #16
Jerrrry wrote: post #6

assuming unbounded time and memory. not being pedantic. you can exhaustively enumerate all inputs for a program. tautologically self-references aside, axiomatically, yes, we can determine if a program will halt, if it has a finite amount of time, or memory. if it doesn't [have unbounded range], then it must [terminate], but it is very, very, very hard to determine if that is the case. but not impossible. and this nua…

That's correct. With determinism and finite memory, you must eventually either repeat a previous state, or halt. This is useful. Verifiers which work by symbolic execution examine large numbers of cases they work through the control flow. Each case can contain a large number of states; you only need one case for each control flow pattern. Now, some programs run into combinatorial explosion when you do that. The numbe…

Checking my understanding: Are you saying that the halting problem is computable (if still completely infeasible in general) for all finite deterministic machines, and that the uncomputability of the busy beaver sequence[1] is due to the infinite memory of Turing machines even though the busy beavers themselves are finite?

ETA: wait that doesn't make sense because it's equivalent to computing the busy beaver number for the program under consideration. What am I missing?

[1] I'm aware there's no unique BB sequence, I don't know that the rigorous phrasing is.

Re: Scooping the Loop Snooper (2000)

#22

Post by Stratoscope »

Jerrrry wrote: post #6

assuming unbounded time and memory. not being pedantic. you can exhaustively enumerate all inputs for a program. tautologically self-references aside, axiomatically, yes, we can determine if a program will halt, if it has a finite amount of time, or memory. if it doesn't [have unbounded range], then it must [terminate], but it is very, very, very hard to determine if that is the case. but not impossible. and this nua…

  You say that you are not being pedantic,
  So why does that make me feel so frantic?

  If we need unbounded ranges and time,
  Is that in your lifetime, or possibly mine?

  Someday we have to compare all our notes,
  So none will have learned it only by rote.

Re: Scooping the Loop Snooper (2000)

#23

Post by Animats »

andreareina wrote: post #21
Animats wrote: post #16

Earlier quoted context omitted.

That's correct. With determinism and finite memory, you must eventually either repeat a previous state, or halt. This is useful. Verifiers which work by symbolic execution examine large numbers of cases they work through the control flow. Each case can contain a large number of states; you only need one case for each control flow pattern. Now, some programs run into combinatorial explosion when you do that. The numbe…

Checking my understanding: Are you saying that the halting problem is computable (if still completely infeasible in general) for all finite deterministic machines, and that the uncomputability of the busy beaver sequence[1] is due to the infinite memory of Turing machines even though the busy beavers themselves are finite? ETA: wait that doesn't make sense because it's equivalent to computing the busy beaver number f…

Checking my understanding: Are you saying that the halting problem is computable (if still completely infeasible in general) for all finite deterministic machines

Yes. There's even a practical way to check if a finite deterministic machine has repeated a previous state. Run two of them in parallel, in lockstep so that one takes two steps while the other takes one. If they ever have identical state, they're in a loop. This takes 1.5x the compute power plus 2x as much memory, so it's far cheaper than storing all previous states.

(Some early mainframe era educational interpreter supposedly did this, to stop simple student infinite loops quickly in a batch system.)

Here's a paper on the busy beaver problem which discusses upper bounds.[1] The key here is that the upper bound on states is not computable. However, if you force an upper bound by limiting memory, it becomes computable. But really hard. That paper discusses how very rapidly the number of states grows for that problem.

[1] https://homepages.hass.rpi.edu/heuveb/Teaching/Logic/CompLog...

Re: Scooping the Loop Snooper (2000)

#24

Post by bruce343434 »

Kranar wrote: post #8
Jerrrry wrote: post #6

assuming unbounded time and memory. not being pedantic. you can exhaustively enumerate all inputs for a program. tautologically self-references aside, axiomatically, yes, we can determine if a program will halt, if it has a finite amount of time, or memory. if it doesn't [have unbounded range], then it must [terminate], but it is very, very, very hard to determine if that is the case. but not impossible. and this nua…

This isn't true in any meaningful way and doesn't really make much sense, it's really just repeating the conclusion of the halting problem in the form of an assumption. Any algorithm that halts will do so, by definition, after a finite amount of time and use a finite amount of space, so saying "assuming unbounded time and memory" is begging the question and taking the conclusion as an assumption. The very problem is…

Yes it does. This is about turning the computer from a turing machine into a finite automaton. Finite automata can be analyzed for halting in finite time, turing machines can’t. And computers as we know them are not turing machines (which are by definition infinite) but they are state machines, and finite ones at that.

Re: Scooping the Loop Snooper (2000)

#25

Post by andreareina »

Animats wrote: post #23
andreareina wrote: post #21

Earlier quoted context omitted.

Checking my understanding: Are you saying that the halting problem is computable (if still completely infeasible in general) for all finite deterministic machines, and that the uncomputability of the busy beaver sequence[1] is due to the infinite memory of Turing machines even though the busy beavers themselves are finite? ETA: wait that doesn't make sense because it's equivalent to computing the busy beaver number f…

Checking my understanding: Are you saying that the halting problem is computable (if still completely infeasible in general) for all finite deterministic machines Yes. There's even a practical way to check if a finite deterministic machine has repeated a previous state. Run two of them in parallel, in lockstep so that one takes two steps while the other takes one. If they ever have identical state, they're in a loop.…

I see! I didn't make the connection that bounding the memory necessarily bounds the number of steps as well. Obvious in hindsight.

Re: Scooping the Loop Snooper (2000)

#26

Post by tgv »

Jerrrry wrote: post #6

assuming unbounded time and memory. not being pedantic. you can exhaustively enumerate all inputs for a program. tautologically self-references aside, axiomatically, yes, we can determine if a program will halt, if it has a finite amount of time, or memory. if it doesn't [have unbounded range], then it must [terminate], but it is very, very, very hard to determine if that is the case. but not impossible. and this nua…

You’re talking about FSAs. The fact that we cannot build a real TM is irrelevant.

If you’re only concerned with physically realizable computing: the number of states can easily become too large to be analyzable.

Re: Scooping the Loop Snooper (2000)

#27

Post by Kranar »

bruce343434 wrote: post #24
Kranar wrote: post #8

Earlier quoted context omitted.

This isn't true in any meaningful way and doesn't really make much sense, it's really just repeating the conclusion of the halting problem in the form of an assumption. Any algorithm that halts will do so, by definition, after a finite amount of time and use a finite amount of space, so saying "assuming unbounded time and memory" is begging the question and taking the conclusion as an assumption. The very problem is…

Yes it does. This is about turning the computer from a turing machine into a finite automaton. Finite automata can be analyzed for halting in finite time, turing machines can’t. And computers as we know them are not turing machines (which are by definition infinite) but they are state machines, and finite ones at that.

There is no way to turn a Turing Machine into a finite automaton.

All finite automatons are guaranteed to halt, and do so in linear time. There is nothing to analyze the answer is always true.

Re: Scooping the Loop Snooper (2000)

#28

Post by Jerrrry »

Kranar wrote: post #27
bruce343434 wrote: post #24

Earlier quoted context omitted.

Yes it does. This is about turning the computer from a turing machine into a finite automaton. Finite automata can be analyzed for halting in finite time, turing machines can’t. And computers as we know them are not turing machines (which are by definition infinite) but they are state machines, and finite ones at that.

There is no way to turn a Turing Machine into a finite automaton. All finite automatons are guaranteed to halt, and do so in linear time. There is nothing to analyze the answer is always true.

exhaustively enumerating all inputs (and thus, outputs) to a program does, without infinite time or memory, turn it into an automaton.

you could then, since having gone over EVERY INPUT...conclude Yes or No, that it Does or Doesn't, HALT.

wtf am i missing

Re: Scooping the Loop Snooper (2000)

#29

Post by danielheath »

Jerrrry wrote: post #28
Kranar wrote: post #27

Earlier quoted context omitted.

There is no way to turn a Turing Machine into a finite automaton. All finite automatons are guaranteed to halt, and do so in linear time. There is nothing to analyze the answer is always true.

exhaustively enumerating all inputs (and thus, outputs) to a program does, without infinite time or memory, turn it into an automaton. you could then, since having gone over EVERY INPUT...conclude Yes or No, that it Does or Doesn't, HALT. wtf am i missing

Taking infinite time to determine whether it halts is not considered a valid answer.

When do you give up and decide it’s not going to terminate? Your answer will be wrong for any program which simply waits one second longer.

Re: Scooping the Loop Snooper (2000)

#30

Post by Jerrrry »

danielheath wrote: post #29
Jerrrry wrote: post #28

Earlier quoted context omitted.

exhaustively enumerating all inputs (and thus, outputs) to a program does, without infinite time or memory, turn it into an automaton. you could then, since having gone over EVERY INPUT...conclude Yes or No, that it Does or Doesn't, HALT. wtf am i missing

Taking infinite time to determine whether it halts is not considered a valid answer. When do you give up and decide it’s not going to terminate? Your answer will be wrong for any program which simply waits one second longer.

that part is understood.

a dripping faucet, for example - is it dripping at 10 drips per hour? or 5 drips per hour? did it stop dripping? no way to tell - the period between drops could be one moment longer than you observed - it could had dripped right after you stopped observing it.

this upper limit is called the busy beaver function. but it is only applicable to turing machines, which we don't build, because we don't have an infinite tape.

Post reply on HN