Relationship To Computability
As with the concept of a decidable set, the definition of a decidable theory or logical system can be given either in terms of effective methods or in terms of computable functions. These are generally considered equivalent per Church's thesis. Indeed, the proof that a logical system or theory is undecidable will use the formal definition of computability to show that an appropriate set is not a decidable set, and then invoke Church's thesis to show that the theory or logical system is not decidable by any effective method (Enderton 2001, pp. 206ff.).
Read more about this topic: Decidability (logic)
Famous quotes containing the word relationship:
“It was a real treat when he’d read me Daisy Miller out loud. But we’d reached the point in our relationship when, in a straight choice between him and Henry James, I’d have taken Henry James any day even if Henry James were dead and not much of a one for the girls when living, either.”
—Angela Carter (1940–1992)