# Questions tagged [incompleteness]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
19 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 ...
14k 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 ...
66 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 ...
157 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 ...
70 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 ...
51 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. ...
191 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 ...
5k 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 ...
3k 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 ...
208 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(...
153 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 ...
67 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 ...
141 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 ...