Liste des Groupes | Revenir à theory |
On 10/26/2024 3:02 AM, Mikko wrote:Why just imagein? That is fairly easy to make. In some other lanugagesOn 2024-10-25 13:31:16 +0000, olcott said:Just imagine c functions that have enough memory to compute
On 10/25/2024 3:01 AM, Mikko wrote:It is possible but to say that x is the z'th power of y is overlyOn 2024-10-24 14:28:35 +0000, olcott said:The power operator can be built from repeated operations of
On 10/24/2024 8:51 AM, Mikko wrote:Incompleteness is easier to define if you also add the power operatorOn 2024-10-23 13:15:00 +0000, olcott said:So lets goes the next step and add multiplication to the algorithm:
On 10/23/2024 2:28 AM, Mikko wrote:No, it does not. Incompleteness theorem does not apply to artihmeticOn 2024-10-22 14:02:01 +0000, olcott said:First grade arithmetic can define a successor function
On 10/22/2024 2:13 AM, Mikko wrote:Basically you define that the successor of X is X + 1. The onlyOn 2024-10-21 13:52:28 +0000, olcott said:I already wrote this in C a long time ago.
On 10/21/2024 3:41 AM, Mikko wrote:You may try with an informal foundation but you need to make sureOn 2024-10-20 15:32:45 +0000, olcott said:Not at all. The only theory needed are the operations
The actual barest essence for formal systems and computationsBefore you can start from that you need a formal theory that
is finite string transformation rules applied to finite strings.
can be interpreted as a theory of finite strings.
that can be performed on finite strings:
concatenation, substring, relational operator ...
that it is sufficicently well defined and that is easier with a
formal theory.
The minimal complete theory that I can think of computesThat is easily extended to Peano arithmetic.
the sum of pairs of ASCII digit strings.
As a bottom layer you need some sort of logic. There must be unambifuous
rules about syntax and inference.
It simply computes the sum the same way
that a first grader would compute the sum.
I have no idea how the first grade arithmetic
algorithm could be extended to PA.
primitive function of Peano arithmetic is the successor. Addition
and multiplication are recursively defined from the successor
function. Equality is often included in the underlying logic but
can be defined recursively from the successor function and the
order relation is defined similarly.
Anyway, the details are not important, only that it can be done.
by merely applying first grade arithmetic to the pair
of ASCII digits strings of [0-1]+ and "1".
https://en.wikipedia.org/wiki/Peano_axioms
The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e. an algorithm) is capable of proving all truths about the arithmetic of natural numbers. For any such consistent formal system, there will always be statements about natural numbers that are true, but that are unprovable within the system.
https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems
When we boil this down to its first-grade arithmetic foundation
this would seem to mean that there are some cases where the
sum of a pair of ASCII digit strings cannot be computed.
that only has addition but not multiplication.
The incompleteness theorem is about theories that have quantifiers.
A specific arithmetic expression (i.e, with no variables of any kind)
always has a well defined value.
(just like first grade arithmetic we perform multiplication
on arbitrary length ASCII digit strings just like someone would
do with pencil and paper).
Incompleteness cannot be defined. until we add variables and
quantification: There exists an X such that X * 11 = 132.
Every detail of every step until we get G is unprovable in F.
to the arithmetic. Otherwise the expressions of provability and
incompleteness are more complicated. They become much simpler if
instead of arithmetic the fundamental theory is a theory of finite
strings. As you already observed, arithmetic is easy to do with
finite strings. The opposite is possible but much more complicated.
the multiply operator.
complicated with a first order formula using just addition and
multiplication.
sums and products of ASCII strings of digits using the same
method that people do.
Les messages affichés proviennent d'usenet.