Tagged Questions
0
votes
1answer
167 views
Godel number and expressibility [duplicate]
how to show that these properties of strings of symbols are expressible:
1) being a term,
2) being a formula
3) being a sentence
4) being a proof in PA
and where a property (i.e., predicate) P of ...
11
votes
3answers
170 views
What is necessary to exchange messages between aliens? [closed]
Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
1
vote
1answer
131 views
Expressibility and numbering
A predicate $P$ is expressible (in PA) if there exists a formula $\phi(x_1,\ldots, x_n)$ of $L_A$ such that for all $m_1,\ldots, m_n$ elements of $\mathbb{N}$, we have that $P(m_1,\ldots, m_n)$ holds ...
1
vote
1answer
151 views
Second incompleteness and Model theorey
If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that ...
3
votes
2answers
84 views
Are axioms and rules of inference interchangeable?
There is an equivalence between cellular automata and formal systems, you can code one into the other and vice versa. But in the the cellular automata (CA) the rules of inference are fixed and are ...
2
votes
2answers
123 views
Beyond Goedel incompleteness and lack of soundness/completeness of higher-order logics
As I understand that there are at least two fundamental limits of the development of the mathematics:
1) Goedel incompeleteness theorems (or more clearly Church thesis) effectively says that there ...
0
votes
0answers
156 views
binary string delta zero case
How to show that the binary string representing z is equal to the concatenation of the binary strings representing x and y (in that order), is a delta-zero condition?
For delta-zero, there must be ...
0
votes
1answer
46 views
Proving By reduction from the Halting Problem
I want to solve the following exercise in Computability and Complexity Theory:
By providing a reduction from the HALTING problem to REACHABLE-CODE,
prove that REACHABLE-CODE is undecidable.
...
1
vote
2answers
137 views
Sequences of a computable function
Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
3
votes
3answers
226 views
How to start with automated theorem proving?
I'm interested in this question, but I'm not going to list my knowledge/demands but rather gear it to more general purpose; so the first thing concerns the prerequisites, i.e.
How much ...
2
votes
2answers
26 views
Get A⊕(B+1) from A⊕B
I have numbers A,B,C.D.
(⊕ is XOR)
C = A⊕B
D = A⊕(B+1)
Is there any way to get D from C, when I do not know A and B? How?
Thanks for help!
3
votes
1answer
38 views
Which categories correspond to the untyped and typed lambda calculus?
Simply typed lambda calculus is the internal language of Cartesian Closed Categories.
What category has its internal language the typed lambda calculus? And the untyped lambda calculus? Can we in ...
5
votes
3answers
179 views
How are the full semantics of SOL and HOL specified?
In relation to this question about the "fundamental" character of possible logical systems, I realized that I just had an intuitive (and so, inadequate) understanding of the way logics higher than FOL ...
1
vote
1answer
54 views
Applying substitutions in lambda calculus
For computing $2+3$, the lambda calculus goes the following: $(\lambda sz.s(sz))(\lambda wyx.y(wyx))(\lambda uv.u(u(uv)))$
I am having a hard time substituing and reaching the final form of $(\lambda ...
0
votes
1answer
78 views
Decimal expansion in logic Church thesis
How can we show that the function $n \mapsto e_n$, where $e_n$ is the $n$-th digit in the decimal expansion of $e$, is computable?
I have some idea in terms of Cantor's diag. argument, but I need to ...
