File Coverage

blib/lib/Acme/HaltingProblem.pm

Criterion	Covered	Total	%
statement	16	17	94.1
branch	4	6	66.6
condition			n/a
subroutine	4	4	100.0
pod	2	2	100.0
total	26	29	89.6

package Acme::HaltingProblem;

use strict;
use vars qw($VERSION);

$VERSION = "1.00";

sub new {
	my $class = shift;
	my $self = ($#_ == 0) ? { %{ (shift) } } : { @_ };
	die "No code provided for analysis" unless $self->{Machine};
	$self->{Input} = [ ] unless ref($self->{Input}) eq 'ARRAY';
	return bless $self, $class;
}

sub analyse {
	my $self = shift;
	eval { $self->{Machine}->(@{ $self->{Input} }); };
	return 1;
}

=head1 NAME

Acme::HaltingProblem - A program to decide whether a given program halts

=head1 SYNOPSIS

	use Acme::HaltingProblem;
	my $problem = new Acme::HaltingProblem(
		Machine	=> sub { ... },
		Input	=> [ ... ],
			);
	my $solution = $problem->solve();

=head1 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.

=over 4

=item 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.

=item $problem->analyse()

Analyse the instance of the halting problem. If it halts, the method
will return 1. Otherwise, it will not return 1.

=head1 BUGS

This code does not correctly deal with the case where the machine
does not halt.

=head1 TODO

It would be nice if this module accepted instances of Acme::Turing.

=head1 SUPPORT

Mail the author at

=head1 AUTHOR

	Shevek
	CPAN ID: SHEVEK
	[e-mail]
	http://www.anarres.org/projects/

=head1 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__;