On Mon, Oct 4, 2010 at 8:56 AM, Patrick Li wrote:
>
> So this seems rather positive. Through some clever search algorithms, or
> heuristics, we can have a infinite-loop checker that works well enough in
> practice.
Um, no. You have to restrict the problem space, too.
For fun, here is a little p
2010/10/4 Marco Morazan :
> What year of study are you in?
>
> I will assume you are a beginner. It can't be done in Racket or any
> other programming language. Most Automata Theory books have a proof of
> that The Halting Problem is unsolvable.
Which by the way explains why companies like B&O (Ba
But ACL2 is a far better match for someone on this list.
On Mon, Oct 4, 2010 at 1:49 PM, Hendrik Boom wrote:
> On Mon, Oct 04, 2010 at 12:12:02PM -0400, Matthias Felleisen wrote:
>>
>> Patrick, in principle you're not mistaken to ask for a 'loop checker'.
>> Many people work on this topic -- desp
On Mon, Oct 04, 2010 at 12:12:02PM -0400, Matthias Felleisen wrote:
>
> Patrick, in principle you're not mistaken to ask for a 'loop checker'.
> Many people work on this topic -- despite the Halting Problem -- to this
> day, mostly in language contexts that are connected to theorem proving
> (or
Patrick, in principle you're not mistaken to ask for a 'loop checker'.
Many people work on this topic -- despite the Halting Problem -- to this
day, mostly in language contexts that are connected to theorem proving
(or logic programming, which is close).
If you're really interested, start with
On Mon, Oct 4, 2010 at 12:02 PM, Stephen Bloch wrote:
> I don't know how much progress has been made on loop-checkers that "work
> well enough in practice."
I think the most practical work here is Microsoft's Terminator
project: https://research.microsoft.com/en-us/um/cambridge/projects/termina
On Oct 4, 2010, at 11:56 AM, Patrick Li wrote:
> Thanks for explaining that to me. I never actually looked up the formal
> definition of Turning-Completeness before.
>
> So this seems rather positive. Through some clever search algorithms, or
> heuristics, we can have a infinite-loop checker t
Thanks for explaining that to me. I never actually looked up the formal
definition of Turning-Completeness before.
So this seems rather positive. Through some clever search algorithms, or
heuristics, we can have a infinite-loop checker that works well enough in
practice.
-Patrick
On Mon, Oct 4
Yep, but the state space is a wee bit large to record :-).
(All computers are equivalent to finite automata in theory, but definitely
not in practice!)
Ed
On Mon, Oct 04, 2010 at 10:31:36AM -0400, Patrick Li wrote:
>I know of the halting problem but can't figure out this dilemma.
>Imagin
right ;)
-- Éric
On Oct 4, 2010, at 10:02 AM, Stephen Bloch wrote:
>
>
> On Oct 4, 2010, at 8:37 AM, Eric Tanter wrote:
>
>> Just for the sake of precision:
>>
>> On Oct 3, 2010, at 11:48 PM, Stephen Bloch wrote:
>>> But there is NO program, in ANY language, that takes in another program a
Hi Patrick,
The problem (Assuming I understand your message properly. :-) ) is that
once you bound the memory, you no longer have a Turing-complete
language. A program on my desktop machine can be expressed as a (very
large) DFA. The halting problem for these DFAs is decidable (even if it
mi
I know of the halting problem but can't figure out this dilemma.
Imagine you load a program into a virtual machine.
This virtual machine has no registers. All operations are done through the
memory.
That is, the entire state of the virtual machine is captured by whatever is
in memory.
In that c
On Oct 4, 2010, at 8:37 AM, Eric Tanter wrote:
> Just for the sake of precision:
>
> On Oct 3, 2010, at 11:48 PM, Stephen Bloch wrote:
>> But there is NO program, in ANY language, that takes in another program and
>> always tells correctly (in finite time) whether that other program contains
Just for the sake of precision:
On Oct 3, 2010, at 11:48 PM, Stephen Bloch wrote:
> But there is NO program, in ANY language, that takes in another program and
> always tells correctly (in finite time) whether that other program contains
> an infinite loop.
The "in ANY language" is too much: Th
Perhaps the original poster was just asking for how to check for the
occurrence of a loop in a graph, presumably in the context of traversing
it.
At least that's how I understood his mail when I first read it -- now
I'm no longer so sure.
Best,
Erich
On Sun, 2010-10-03 at 23:48 -0400, Stephen
On Oct 3, 2010, at 7:19 PM, Marco Morazan wrote:
> What year of study are you in?
>
> I will assume you are a beginner. It can't be done in Racket or any
> other programming language. Most Automata Theory books have a proof of
> that The Halting Problem is unsolvable.
More precisely, you can wr
What year of study are you in?
I will assume you are a beginner. It can't be done in Racket or any
other programming language. Most Automata Theory books have a proof of
that The Halting Problem is unsolvable.
Marco
On Sun, Oct 3, 2010 at 5:22 PM, A Z wrote:
> Hello,
> Does anybody know how to
Don't be harsh on yourself. This one's a bit subtle. I'd have missed it, too.
Shriram
On Sun, Oct 3, 2010 at 6:44 PM, Robby Findler
wrote:
> Actually I think this one is a bug I recently introduced in that code.
> I'll try to fix it soon.
>
> Robby
>
> On Sun, Oct 3, 2010 at 5:43 PM, Eli Barzi
(For the curious, I was using my polytime reduction from travelling
salesman to sorting and then searching the space of terminating
programs for the given program.)
Robby
On Sun, Oct 3, 2010 at 5:44 PM, Robby Findler
wrote:
> Actually I think this one is a bug I recently introduced in that code.
Actually I think this one is a bug I recently introduced in that code.
I'll try to fix it soon.
Robby
On Sun, Oct 3, 2010 at 5:43 PM, Eli Barzilay wrote:
> Two minutes ago, Robby Findler wrote:
>> How does it do on this program:
>>
>> (begin (sleep 5) 'done)
>>
>> ?
>
> Yeah, it has some false
Two minutes ago, Robby Findler wrote:
> How does it do on this program:
>
> (begin (sleep 5) 'done)
>
> ?
Yeah, it has some false positives. I need to update it with the
recent halting problem solution code.
--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
On 10/03/2010 02:22 PM, A Z wrote:
> Does anybody know how to check for infinite loops programmatically in
> racket?
To check for... wat
http://en.wikipedia.org/wiki/Halting_problem
_
For list-related administrative tasks:
http://lists.racket-la
How does it do on this program:
(begin (sleep 5) 'done)
?
Robby
On Sun, Oct 3, 2010 at 5:31 PM, Eli Barzilay wrote:
> An hour ago, A Z wrote:
>> Hello,
>>
>> Does anybody know how to check for infinite loops programmatically in
>> racket?
>
> -> (require racket/sandbox)
> -> (sandbox-eval-li
An hour ago, A Z wrote:
> Hello,
>
> Does anybody know how to check for infinite loops programmatically in
> racket?
-> (require racket/sandbox)
-> (sandbox-eval-limits '(4 10)) ; 4sec 10mb
-> (define e (make-evaluator 'racket))
-> (e '((lambda (x) (x x)) (lambda (x) (x x
with-limit: out of t
It's pretty easy once you're used to call/cc.
Shriram
On Sun, Oct 3, 2010 at 5:22 PM, A Z wrote:
> Hello,
> Does anybody know how to check for infinite loops programmatically in
> racket?
> Thanks,
> Colum
> _
> For list-related administrative tas
25 matches
Mail list logo
