Questions tagged [incompleteness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
40 views

Why we can't use deduction theorem on soundness to contravene second incompleteness with lob's theorem

I'm starting to learn modal logic and there is something that's bothering my mind for a while. we know from deduction theorem that $((\vdash q) \rightarrow (\vdash p)) \Leftrightarrow(\vdash (q \...
user avatar
0 votes
0 answers
44 views

Can you write an algorithm that can generalize another algorithm?

Can you write an algorithm which can take in a given function/algorithm, and produce a distribution of generalizations of the function at hand? One such simple example of generalization might mean the ...
user avatar
1 vote
1 answer
28 views

Many-one reductions between the set of true sentences and a particular arithmetical set

Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic. Let TH(N) = {ϕ : ϕ is a first order sentence ...
user avatar
2 votes
1 answer
135 views

Did Wheeler really believe that physics was undecidable?

John Archibald Wheeler was a famous physicist. It has been stated that he thought that there was a strong connection between undecidability and quantum physics: This idea was given an early ...
user avatar
  • 21
-1 votes
1 answer
71 views

Caroll's paradox => Rice theorem?

To me (but I might be wrong) Rice's theorem asserts that it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language within the same given language. ...
user avatar
  • 109
6 votes
1 answer
271 views

Relation between "undecidability of arithmetic" and "godel's incompleteness theorem"?

There is a theorem that states that arithmetic is undecidable: i.e. $Th(\mathcal N)$, the set of all sentences in the standard arithmetic structure $\mathcal N=(\mathbb N,+,\cdot , 0,1)$ where the ...
user avatar
  • 3,474
2 votes
2 answers
86 views

Does Gödel's first incompleteness theorem apply to quantifier-free arithmetics?

Gödel's first incompleteness theorem states roughly that "for any axiomatization of arithmetic, there are statements that can neither be proven to be false nor true." Does this still hold when it ...
user avatar
  • 3,474
3 votes
1 answer
230 views

Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations?

I have heard whisperings that if we have a turing machine that is allowed to compute infinitely many steps in finite time, then we can solve the halting problem. This made me wonder, if we have such ...
user avatar
  • 3,474
19 votes
4 answers
6k views

Can proof by contradiction work without the law of excluded middle?

I was recently thinking about the validity of proof by contradiction. I’ve read for the past few days things on intuitionistic logic and Godel’s theorems to see if they would provide me answers to my ...
user avatar
13 votes
5 answers
4k views

Why does soundness imply consistency?

I was reading the question Consistency and completeness imply soundness? and the first statement in it says: I understand that soundness implies consistency. Which I was quite puzzled about ...
user avatar
5 votes
1 answer
235 views

Analogy between Gödel's incompleteness proof and Richard's argument

If we take a look at Gödel's paper “On formally undecidable propositions”, the first self referential proof given in the paper, with the following formula: $$n \in K \equiv \overline{\textit{Bew}}[R(...
user avatar
-1 votes
3 answers
160 views

Is Goedel's 1st theorem not algorithmically derivable?

First let me explain what I mean by algorithmically derivable. An algorithm must be able to come up with the proof without prior knowledge of the proof, in the same way mathematicians and computer ...
user avatar
  • 1,379
0 votes
1 answer
70 views

Axioms - proof of halt

I am new to this forum and this is my first post. I am interested in solving a problem, but cannot find the way to think about it. If anyone can guide me through it, I would be obliged: Let F be some ...
user avatar
7 votes
1 answer
1k views

Understanding of Turing's Answer to the Entscheidungsproblem

I apologize if this question has been asked before, but I was not able to find a duplicate. I have just finished reading The Annotated Turing and I am a bit confused. From what I understand, the ...
user avatar
  • 208
5 votes
1 answer
194 views

Is there a decidable problem which has a proof that it cannot be proved to have a particular deciding Turing machine?

I came across the question Is there an algorithm that provably exists although we don't know what it is? I was able to follow the example "Given an integer $n\ge0$ is there a run of $n$ or more ...
user avatar
-2 votes
1 answer
255 views

Why decision problem definition ignores Gödel incompleteness theorem?

The following question assume that the decision problem definition (syntactic) has been written (and could be changed if it isn't able) to catch a concept (meaning, semantic) which has both nice ...
user avatar
  • 669
85 votes
6 answers
15k views

Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

I've always thought vaguely that the answer to the above question was affirmative along the following lines. Gödel's incompleteness theorem and the undecidability of the halting problem both being ...
user avatar