Date: 2007-01-07 07:43 am (UTC)
From: [identity profile] cema.livejournal.com
In order to fix the compiler, of course! ;-)

Date: 2007-01-07 02:52 pm (UTC)
From: [identity profile] anhinga-anhinga.livejournal.com
In Standard ML the problem is decidable, it's just that the worst case is that the derived type is exponential in the length of the program (as a directed acyclic graph, and double exponential as linear output).

So one needs a bit less than Turing oracle to fix the compiler, at least for Standard ML ;-) Some other type systems are actually undecidable.

But at the same time, I am not sure that Turing oracle by itself can be used to reduce the complexity of the computation involved to make it fit a real computer -- I am just not familiar enough with the theory of computations with such oracles.. For example, if one uses such an oracle in a straightforward way, as applied to this problem, the oracle always says "yes" (a large enough computer will always complete type inference of a Standard ML program given enough time), and this does not help us to reduce the resources needed to figure out the outcome of the type inference process.

Date: 2007-01-07 05:43 pm (UTC)
From: [identity profile] anhinga-anhinga.livejournal.com
Actually, it is possible to use the Turing oracle to determine whether the outcome of a program is a particular value: one just modifies the program to loop after any other outcome, and applies the oracle..

Profile

anhinga_anhinga: (Default)
anhinga_anhinga

July 2021

S M T W T F S
    123
45678910
11121314151617
18 192021222324
25262728293031

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 6th, 2025 08:36 pm
Powered by Dreamwidth Studios