NAME
Acme::HaltingProblem - A program to decide whether a given program halts
SYNOPSIS
use Acme::HaltingProblem;
my $problem = new Acme::HaltingProblem(
Machine => sub { ... },
Input => [ ... ],
);
my $solution = $problem->solve();
DESCRIPTION
The Halting Problem is one of the hardest problems in computing. The
problem, approximately stated, is thus:
Given an arbitrary Turing Machine T and input for that turing
machine D, decide whether the computation T(D) will terminate.
new Acme::HaltingProblem(...)
Construct a new instance of the halting problem where the Machine is
given as an arbitrary subref, and the Input is a reference to a list
of arguments.
$problem->analyse()
Analyse the instance of the halting problem. If it halts, the method
will return 1. Otherwise, it will not return 1.
BUGS
This code does not correctly deal with the case where the machine
does not halt.
TODO
It would be nice if this module accepted instances of Acme::Turing.
SUPPORT
Mail the author at
AUTHOR
Shevek
CPAN ID: SHEVEK
cpan@anarres.org
http://www.anarres.org/projects/
COPYRIGHT
Copyright (c) 2002 Shevek. All rights reserved.
This program is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.
1; __END__;