Which aong the following are undecidable theories?(a) The first order theory of boolean algebra(b) The first order theory of Euclidean geomentry(c) The first order theory of hyperbolic geometry(d) The first order theory of the natural number with addition, multiplication, and equalityI have been asked this question in exam.Query is from The Universal Language-Undecidability topic in section Undecidability of Automata Theory

Which aong the following are undecidable theories?(a) The first order

1.	Which aong the following are undecidable theories?(a) The first order theory of boolean algebra(b) The first order theory of Euclidean geomentry(c) The first order theory of hyperbolic geometry(d) The first order theory of the natural number with addition, multiplication, and equalityI have been asked this question in exam.Query is from The Universal Language-Undecidability topic in section Undecidability of Automata Theory
Answer» The correct option is (d) The first order theory of the natural number with addition, multiplication, and equality To explain I would say: Tarski and Mostowski in 1949, established that the first order theory of natural NUMBERS with addition, multiplication, and equality is an undecidable theory. OTHERS MENTIONED are decidable THEORIES.

Discussion

No Comment Found

Related InterviewSolutions

The class of recursive language is known as:(a) R(b) RC(c) RL(d) All of the mentionedThis question was posed to me in a national level competition.This question is from The Universal Language-Undecidability topic in section Undecidability of Automata Theory
Decidable can be taken as a synonym to:(a) recursive(b) non recursive(c) recognizable(d) none of the mentionedThe question was asked in a job interview.I'd like to ask this question from The Universal Language-Undecidability topic in section Undecidability of Automata Theory
The language accepted by a turing machine is called ____________(a) Recursive Ennumerable(b) Recursive(c) Both (a) and (b)(d) None of the mentionedThe question was posed to me in an interview for job.Question is taken from The Universal Language-Undecidability topic in division Undecidability of Automata Theory
Which among the following are semi decidable?(a) Empty-DFA(b) Rec-NFA(c) Infinite-DFA(d) All of the mentionedI got this question in an internship interview.I would like to ask this question from The Universal Language-Undecidability topic in chapter Undecidability of Automata Theory
Which of the following technique is used to find whether a natural language isnt recursive ennumerable?(a) Diagonalization(b) Recursive Induction(c) Both (a) and (b)(d) None of the mentionedThe question was asked during an interview for a job.This intriguing question originated from The Diagonalization Languages topic in chapter Undecidability of Automata Theory
Recursive languages are also known as:(a) decidable(b) undecidable(c) sometimes decidable(d) none of the mentionedI have been asked this question by my school teacher while I was bunking the class.This question is from The Universal Language-Undecidability in section Undecidability of Automata Theory
Which of the following are incorrect options?(a) Informally, problem is a yes/no question about an infinite set of possible instances(b) Formally, a problem is a language(c) Both (a) and (b)(d) None of the mentionedThis question was addressed to me during an online interview.My question is taken from The Diagonalization Languages in division Undecidability of Automata Theory
A formal language is recursive if :(a) a total turing machine exists(b) a turing machine that halts for every input(c) turing machine rejects if the input does not belong to the language(d) all of the mentionedThe question was asked during an interview for a job.The origin of the question is The Universal Language-Undecidability in chapter Undecidability of Automata Theory
A problem is called __________ if its has an efficient algorithm for itself.(a) tractable(b) intractable(c) computational(d) none of the mentionedI have been asked this question in an interview.This intriguing question comes from The Universal Language-Undecidability topic in portion Undecidability of Automata Theory
If a problem has an algorithm to answer it, we call it _________(a) decidable(b) solved(c) recognizable(d) none of the mentionedThis question was posed to me in homework.My query is from The Diagonalization Languages in section Undecidability of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment