bio | website | |
---|---|---|
location | Germany | |
age | 48 | |
visits | member for | 4 years, 9 months |
seen | 4 hours ago | |
stats | profile views | 3,310 |
My interests:
abstract structures
(e.g. graphs, groups, polytopes, spaces, ...)
^{in the course of this}category theory
model theory
presentations and representations
(e.g. of abstract structures by or inside other abstract structures)
^{next to this}philosophy
(esp. of mathematics, science, and mind)
^{especially concerned with}atomism
(i.e. reductionistic or other theories referring to some kind of "atoms")- ancient atomism
- set theories (with and without urelements)
- logical atomism
- particle physics
- neuroscience
^{and}
their refutations
Sep 3 |
awarded | Peer Pressure |
Aug 30 |
comment |
When are two algorithms essentially the same?
I didn't want to ask for a single equivalence, sorry if it sounded like this. I am looking for any (sensible) equivalence. One came to my mind only today: $T$ is equivalent to $T'$ when they have the same symbols and blank symbol, compute the same function, have the same number of internal states and there is a bijection $f$ between the states that preserves - among other things - starting and halting, next state $S(f(x),s)$ is $f(S(x),s)$, and so on. One may find this trivial, but it is a sensible equivalence, isn't? And there may be others. |
Aug 29 |
comment |
When are two algorithms essentially the same?
If the question is read "which definition of equivalence between unary addition Turing machines is sensible?" there is an answer (and you gave it): none but the trivial one: all such machines (defined by their input-output behaviour) are equivalent. And indeed they are: they compute the same function. |
Aug 29 |
comment |
When are two algorithms essentially the same?
Why not did you simply answer by "none" (= one might want to apply no definition of equivalence). A real answer to a real question. |
Aug 28 |
asked | When are two algorithms essentially the same? |
Aug 26 |
comment |
Rationale behind an requirement on Turing machines
Yet another question: Does your answer imply that my $T_{bin-double}$ computes nothing, thus is no Turing machine at all? And what about $T_{id}$ which rewrites the first symbol and halts? $T_{id}$ seems to work equally well for unary and binary and arbitrary $k$-ary (interpreted) inputs. |
Aug 26 |
comment |
Rationale behind an requirement on Turing machines
You seem to imply that one does not really need to require a blank symbol? So what is your specific answer? "In fact one does not need to require a blank symbol because there are encoding schemes that allow to neglect them?" How can this meta-mathematical statement be made totally precise? |
Aug 26 |
comment |
Rationale behind an requirement on Turing machines
Yes, this is what I mean. But you put the head initially on a specific square (left or equal to the first $1$). |
Aug 26 |
comment |
Rationale behind an requirement on Turing machines
One question: you write "input is padded with infinitely many additional $0$s". How can this be, when we have only finitely many $1$s? |
Aug 26 |
comment |
Rationale behind an requirement on Turing machines
@Joel: Thank you very much! (Now, that I know and understand your answer, I see that my question was not really "research level". Do you find it inappropriate for MO, too?) |
Aug 26 |
accepted | Rationale behind an requirement on Turing machines |
Aug 26 |
revised |
Rationale behind an requirement on Turing machines
edited tags |
Aug 26 |
comment |
Rationale behind an requirement on Turing machines
Is it "un-mathematical thinking" to think about the reasons why a condition in a definition was chosen? Maybe it's "meta-mathematical thinking", but it's "mathematical" nevertheless, isn't it? Should I ask the question at meta.mathoverflow.net? |
Aug 26 |
comment |
Rationale behind an requirement on Turing machines
If the answer to this question is too obvious, any hint would be welcome why. (Or any hint why this question disqualifies?) |
Aug 26 |
revised |
Rationale behind an requirement on Turing machines
edited body |
Aug 26 |
asked | Rationale behind an requirement on Turing machines |
Aug 25 |
comment |
“Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski]
Thanks, Emil, this rounds off the picture. |
Aug 25 |
comment |
“Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski]
There are three results involved: (1) $\mid$ is definable by $+$, (2) $\cdot$ is definable by $+$ and $\mid$, (3) Büchi's result. Is it known which of these results were known to R. Robinson? (Büchi's result most probably not.) |
Aug 25 |
revised |
“Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski]
added 174 characters in body |
Aug 25 |
asked | “Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski] |