Questions tagged [incompleteness]
The incompleteness tag has no usage guidance.
21 questions
1
vote
2
answers
72
views
Gödel's theorem and machines' power
I was studying AI and when a question came to my mind.
I know that one of the objections to the possibility of a thinking machine examined by Turing is the so called mathematical objection, ...
- 111
5
votes
7
answers
3k
views
What are the conditions necessary for a programming language to have no undefined behavior?
For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question ...
2
votes
3
answers
367
views
Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?
If I understand correctly, the first incompleteness theorem says that any "effectively axiomatized" formal system which is consistent must contain theorems which are independent of the ...
1
vote
1
answer
72
views
Self-referential systems cannot predict their future behaviour? (reference request)
Seth Lloyd claims in this video that free will stems from our impossibility of determining how a system capable of self-reference will behave in the future (e.g. whether a human being will have chosen ...
- 111
1
vote
1
answer
62
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 \...
0
votes
0
answers
47
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 ...
- 135
1
vote
1
answer
29
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 ...
2
votes
1
answer
174
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 ...
- 21
-1
votes
1
answer
80
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. ...
- 119
6
votes
1
answer
538
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 ...
- 4,122
2
votes
2
answers
102
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 ...
- 4,122
3
votes
1
answer
322
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 ...
- 4,122
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 ...
- 3,090
13
votes
5
answers
5k
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 ...
- 3,090
5
votes
1
answer
243
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(...
- 317
-1
votes
3
answers
167
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 ...
- 1,447
0
votes
1
answer
73
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 ...
- 17
7
votes
2
answers
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 ...
- 208
5
votes
1
answer
230
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 ...
- 2,992
-2
votes
1
answer
287
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 ...
- 679
95
votes
6
answers
19k
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 ...
- 1,053