The Experts below are selected from a list of 27 Experts worldwide ranked by ideXlab platform
Bhupinder Singh Anand - One of the best experts on this subject based on the ideXlab platform.
-
Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?
arXiv: General Mathematics, 2005Co-Authors: Bhupinder Singh AnandAbstract:We consider the thesis that an arithmetical relation, which holds for any, given, assignment of natural numbers to its free variables, is Turing-decidable if, and only if, it is the standard representation of a PA-Provable Formula. We show that, classically, such a thesis is, both, unverifiable and irrefutable, and, that it implies the Turing Thesis is false; that Goedel's arithmetical predicate R(x), treated as a Boolean function, is in the complexity class NP, but not in P; and that the Halting problem is effectively solvable, albeit not algorithmically.
-
Can Laplace's Formula model a deterministic universe that is irreducibly probabilistic?
arXiv: General Mathematics, 2003Co-Authors: Bhupinder Singh AnandAbstract:If we assume the Thesis that any classical Turing machine T, which halts on every n-ary sequence of natural numbers as input in a determinate time t(n), determines a PA-Provable Formula, whose standard interpretation is an n-ary arithmetical relation f(x1, ..., xn) that holds if, and only if, T halts, then we can define Laplace's Formula recursively such that it can model the state of a deterministic quantum universe that is irreducibly probabilistic.
-
Is a deterministic universe logically consistent with a probabilistic Quantum Theory
arXiv: General Mathematics, 2002Co-Authors: Bhupinder Singh AnandAbstract:If we assume the Thesis that any classical Turing machine T, which halts on every n-ary sequence of natural numbers as input, determines a PA-Provable Formula, whose standard interpretation is an n-ary arithmetical relation f(x1, >..., xn) that holds if, and only if, T halts, then standard PA can model the state of a deterministic universe that is consistent with a probabilistic Quantum Theory. Another significant consequence of this Thesis is that every partial recursive function can be effectively defined as total.
Sachio Hirokawa - One of the best experts on this subject based on the ideXlab platform.
-
LFCS - Balanced Formulas, BCK-Minimal Formulas and Their Proofs
Logical Foundations of Computer Science — Tver '92, 1992Co-Authors: Sachio HirokawaAbstract:The structure of normal form proof figures are investigated for implicatonal Formulas in BCK-logic, in which each assumption can be used at most once. Proof figures are identified with λ-terms. A Formula is balanced iff no type variable occurs more than twice in it. It is known that proof figure in βη-normal is unique for balanced Formulas. In this paper, it is shown that closed λ-terms in β-normal form having balanced types are BCK-λ-terms in which each variable occurs at most once. A Formula is BCK-minimal iff it is BCK-Provable and it is not a non-trivial substitution instance of other BCK-Provable Formula. It is also shown that the set BCK-minimal Formulas is identical to the set of principal type-schemes of BCK-λ-terms in βη-normal form.
John C. Shepherdson - One of the best experts on this subject based on the ideXlab platform.
-
A note on the notion of truth in fuzzy logic
Annals of Pure and Applied Logic, 2001Co-Authors: Petr Hájek, John C. ShepherdsonAbstract:Abstract In fuzzy predicate logic, assignment of truth values may be partial, i.e. the truth value of a Formula in an interpretation may be undefined (due to lack of some infinite suprema or infima in the underlying structure of truth values). A logic is supersound if each Provable Formula ϕ is true (has truth value 1) in each interpretation in which the truth value of ϕ is defined. It is shown that among the logics given by continuous t -norms, Godel logic is the only one that is supersound; all others are (sound but) not supersound. This supports the view that the usual restriction of semantics to safe interpretations (in which the truth assignments is total) is very natural.
Herman Ruge Jervell - One of the best experts on this subject based on the ideXlab platform.
-
CSL - Recursive Inseparability in Linear Logic
Computer Science Logic, 1993Co-Authors: Stål Aanderaa, Herman Ruge JervellAbstract:We first give our version of the register machines to be simulated by proofs in propositional linear logic. Then we look further into the structure of the computations and show how to extract ”finite counter models” from this structure. In that way we get a version of Trakhtenbrots theorem without going through a completeness theorem for propositional linear logic. Lastly we show that the interpolant I in propositional linear logic of a Provable Formula A ⊸ B cannot be totally recursive in A and B.
Heinrich Wansing - One of the best experts on this subject based on the ideXlab platform.
-
Sequent Systems for Trilattice Logics
Truth and Falsehood, 2011Co-Authors: Yaroslav Shramko, Heinrich WansingAbstract:In the present chapter, we will define various standard and non-standard sequent calculi for logics related to the trilattice SIXTEEN 3. In a first step, we will introduce three sequent calculi G B , F B , and QB for Odintsov’s first-degree proof system ⊢ B presented in the previous chapter. The system G B is a standard Gentzen-type sequent calculus, FB is a four-place (horizontal) matrix sequent calculus, and Q B is a quadruple (vertical) matrix sequent calculus. In contrast with G B , the calculus \(\hbox{F}_B\) satisfies the subFormula property, and the calculus \(\hbox{Q}_B\) reflects Odintsov’s co-ordinate valuations associated with valuations in \(SIXTEEN_3\). The mutual equivalence between \(G_B\), \(\hbox{F}_B, \) and \(\hbox{Q}_B\), the cut-elimination theorems for these calculi, and the decidability of \(\vdash _B\) are proved. In addition, it is shown how the sequent systems for \(\vdash _B\) can be extended to cut-free sequent calculi for Odintsov’s \(L_B\), which is an extension of \(\vdash_B\) by adding classical implication and negation connectives. The axiom systems \(L_T,L_B,L^{f}_{T},L^{f}_{B},{L'}_T,{L'}_B,{{{L}^{f}}'}_{T},\) and \({{{L}^{f}}'}_{B}\) from Chap. 5 are all auxiliary calculi in the sense that they do not capture truth entailment \(\models_t\) or falsity entailment \(\models _f\) in the respective languages. The chief axiom systems are those capturing the semantically defined logics \(L^t,L^f,{L'},{{L}^f}',L^{t*}\) and \(L^{f*}\). In a second step, we will present cut-free sound and complete higher-arity sequent calculi for all these axiom systems. The semantical foundation of these calculi is provided by the co-ordinate valuations. A sequent calculus \({\text{GL}}^*\) for truth entailment in \(SIXTEEN_3\) in the full language \({\fancyscript{L}}^*_{tf}\) is introduced and shown to be sound and complete and admitting of cut-elimination. This sequent calculus directly takes up Odintsov’s presentation of \(SIXTEEN_3\) as a twist-structure over the two-element Boolean algebra and enjoys all the nice properties known from the G3c sequent calculus for classical logic, see Troelstra and Schwichtenberg (Cambridge University Press, Cambridge, 2000). Moreover, a sequent calculus for falsity entailment in \(SIXTEEN_3\) in \({\fancyscript{L}}^*_{tf}\) can be obtained from \({\text{GL}}^{*}\) not by changing any of the inference rules of the system but simply by appropriately changing the notion of a Provable Formula.
