# Questions tagged [provability]

For questions on provability, the capability of being demonstrated or logically proved.

253 questions
Filter by
Sorted by
Tagged with
1 vote
99 views

### Does a Turing machine exist with output 1 if an unprovable statement is true and 0 otherwise?

Suppose there is some statement $X$ that is unprovable in some system, e.g. ZFC. Let $L = \{x : x \in \Sigma^* \land X \text{ is true}\}$. Is there a Turing machine that decides $L$? I have had an ...
23 views

### Proving minimum steps solution for a math quiz [duplicate]

I have the following math quiz: You have 4 Red Balls & 4 Green Balls. You cannot see the color of the balls but you have a machine (or function) which takes 2 balls as input and returns true, when ...
105 views

### Prove $\sqrt{-3+44a} \in N$ can't be a square root of a square of a natural number [closed]

Prove $\sqrt{-3+44a} \in N$ can't be a square root of a square of a natural number. $$\begin{equation*} \begin{cases} a \in N \\ d \in N \\ -3+44a = d^2 \end{cases} \end{equation*}$$
1 vote
67 views

### Is someone trying to solve problems by building all possible proofs using all possible rules of inference?

We obviously can construct a program that, starting with ZFC (or any other theory) axioms, would use all possible rules of inference to get all possible proofs constructible in ZFC. (There would be ...
143 views

### Is there a proposition that cannot be proven to be provable(or not)? [duplicate]

I have been studying mathematical logic and the foundations of formal systems, and I came across the concept of "provability" and "unprovability" of propositions within such ...
39 views

### Estimating Set Size from Sample Data

I encountered a sampling problem and managed to approximate programmatically. However, I'm interested in determining the analytical solution. There are two sets $A$ and $B$. $|A|$ is known, $|B|$ is ...
1 vote
57 views

1 vote
93 views