Computer Science – Logic in Computer Science
Scientific paper
2009-03-25
Computer Science
Logic in Computer Science
Scientific paper
In functional programming languages the use of infinite structures is common practice. For total correctness of programs dealing with infinite structures one must guarantee that every finite part of the result can be evaluated in finitely many steps. This is known as productivity. For programming with infinite structures, productivity is what termination in well-defined results is for programming with finite structures. Fractran is a simple Turing-complete programming language invented by Conway. We prove that the question whether a Fractran program halts on all positive integers is Pi^0_2-complete. In functional programming, productivity typically is a property of individual terms with respect to the inbuilt evaluation strategy. By encoding Fractran programs as specifications of infinite lists, we establish that this notion of productivity is Pi^0_2-complete even for the most simple specifications. Therefore it is harder than termination of individual terms. In addition, we explore possible generalisations of the notion of productivity in the framework of term rewriting, and prove that their computational complexity is Pi^1_1-complete, thus exceeding the expressive power of first-order logic.
Endrullis Joerg
Grabmayer Clemens
Hendriks Dimitri
No associations
LandOfFree
Complexity of Fractran and Productivity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of Fractran and Productivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Fractran and Productivity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-68534