Shevek > Acme-HaltingProblem-1.00 > Acme::HaltingProblem

Download:
Acme-HaltingProblem-1.00.tar.gz

Dependencies

Annotate this POD

CPAN RT

New  2
Open  0
View/Report Bugs
Module Version: 1.00   Source  

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 <cpan@anarres.org>

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

syntax highlighting: