Questions tagged [incompleteness]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
42 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 ...
27 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 ...
121 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 ...
67 views

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. ...
222 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 ...
80 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 ...
222 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 ...
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 ...
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 ...
219 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(...
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 ...
68 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 ...
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 ...
176 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 ...