3,478 reputation
12362
bio website
location Germany
age 48
visits member for 5 years
seen 48 mins ago

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")

  • their refutations


2d
awarded  Yearling
Oct
14
awarded  Self-Learner
Oct
14
answered Supervenience in mathematics
Sep
29
comment Rationale behind an requirement on Turing machines
Notice further, that $b$ can not only be read but also be written.
Sep
29
comment Rationale behind an requirement on Turing machines
Re-reading your answer I am still not satisfied: In Hopcroft/Ullman's definition of a Turing machine as a 7-tupel the blank symbol $b$ is distinguished (among the tape symbols), but there seems to be no requirement on a Turing machine involving $b$. Especially the transition function $\delta$ can be defined on the whole tape alphabet (including $b$). The same holds - by the way - for the initial state $q_0$.
Sep
27
awarded  Nice Answer
Sep
24
awarded  Autobiographer
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?