Distance between equations

From: Piotr Wyderski (piotr.wyderskiREMOVE_at_wp.pl)
Date: 02/28/04

  • Next message: Toby Ord: "Re: Comparing two notions of computable number" 
    Date: Sat, 28 Feb 2004 01:56:34 +0100

    Hello,

    assume that we have a set of integer constants,
    a set of integer variables and some standard integer
    operators: +, -, *, div and mod; we can also use
    parentheses. We can build arbitrarily complex formulas
    using these objects, e.g. x+7*y-z div 2 is a valid formula.
    And the question is: given two formulas, P and Q, is
    it possible to check automatically whether they differ
    only by an integer constant? Put another way: is
    the problem "P-Q=O(1)" decidable?

        Best regards
        Piotr Wyderski

  • Next message: Toby Ord: "Re: Comparing two notions of computable number"