21
votes
Group theory with grep?
I wrote that quote, and I'll take the hint of @SamNead and try to write an answer, although the best I can do is to write a somewhat speculative extension of the story behind the quote, laced with ...
- 15.4k
14
votes
Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?
Let me try to answer the actual question that was asked. The Wikipedia
page
defines inductive Turing machines as follows:
An inductive Turing machine is a definite list of well-defined
...
- 236k
12
votes
Is Post's tag system solved?
Q1: The status of Post's 3-tag system as of 2011 was reviewed by Liesbeth de Mol in On the complex behavior of simple tag systems. An experimental approach. "It is still not known whether this ...
- 188k
12
votes
Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?
Are inductive turing machines physically realizable (at least in the same sense of realizaility of Turing machines as Intel processors with bounded RAM and one that degrades over time)?
Can inductive ...
- 82.7k
10
votes
Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?
This is not an answer to the OP's question, and is a bit of a tangent.
But perhaps relevant concerning the physical realizability issue raised by Joel.
I just today heard a talk on a "Fold-and-Cut ...
- 151k
9
votes
Accepted
Unique words in dihedral groups
The conjecture holds true and I don't know of anything similar.
Given a word $w$ over $\{0, 1\}$, we denote by $\overline{w}$ the word obtained from $w$ by interchanging $0$ and $1$.
Let us show ...
- 7,893
7
votes
Accepted
Verification of Turing-equivalent automata
(a) I think that "no human understands" what the current busiest $6$-state
Busy Beaver
$2$-symbol Turing Machine is doing while it prints
out $3.5 \times 10^{18267}$ $1$'s before halting.
(b) This ...
- 151k
7
votes
Accepted
Is Post's tag system solved?
Here are the two irreducible repeating patterns that Liesbeth de Mol discovered, together with a third high-period irreducible repeating pattern discovered by Rich Schroeppel:
$b^3 a^5 b^5$ (period ...
- 12.4k
5
votes
Group theory with grep?
As Derek Holt suggested in a comment, it seems Thurston was indeed thinking of word acceptors that returned normal forms for elements of automatic groups. From a 1989 research report of his titled ...
- 737
5
votes
Accepted
Language equivalence between deterministic and non-deterministic counter net
The short answer is that as far as I'm aware, this question is open.
It is however very close to ones that are settled. I provide some more detail below.
As you've correctly pointed out, the ...
5
votes
Accepted
Understanding Syntactic Congruence & Order
If you have the minimal automaton, then two words are syntactically equivalent iff from any give state they lead to the same state. Therefore the syntactic monoid is the monoid generated by the ...
- 38.6k
4
votes
Accepted
Counter net decidability
This is a partial answer (see note 2 below), but mostly an attempt to rephrase the question into something both meaningful and understandable, so that hopefully someone can answer it.
Let $\sigma$ be ...
- 32.5k
3
votes
Origin of tropical mathematics
I asked Christian Choffrut and Dominique Perrin this question today. They essentially told me the following: certainly, the name tropical comes in honour of the Brazilian mathematician Imre Simon; and ...
3
votes
Multi-head two-way finite automata versus logarithmic space
The following paper contains a proof (p. 191-192):
Sudborough, I. H. Some remarks on multihead automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 11.3 (...
- 1,646
3
votes
Is there a physically realizable inductive turing machine that can solve Hilbert's $10$th problem and can it overcome Church-Turing Hypothesis?
Consider the following paper, written by A. Steven Younger, Emmett Redd, Hava Siegelmann, and Conrad Bell:
"A Physical Machine Based on a Super-Turing Computational Model" [found under title on the ...
- 6,132
3
votes
Giving the same concept different names in the same paper
First, I agree with the commenters in not understanding your objection to giving different names to the same mathematical objects if they are used to model different phenomena. The terms "position" ...
- 4,529
3
votes
Accepted
Embedding Turing machine
Let $\mathcal{M}$ be a class of binary functions acting on strings in $\Sigma^*$,
along with a "size" function $|\cdot|:\mathcal{M}\to\{1,2,\ldots\}$ with the property that there are only finitely ...
- 6,541
3
votes
Accepted
If a language $L$ is accepted by a non-deterministic automation, then $L$ is regular
Wikipedia and Hopcroft and Ullman require a unique start state for their NFA's. You can transform an NFA with many start states into an NFA with just one by adding a new state $q_0$ and connecting it ...
- 28.1k
2
votes
Accepted
For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset
This is proved in Section 4 of Kari's paper here.
Essentially the same proof is in chapter 15 of my book the Representation Theory of Finite Monoids done from a more representation theoretic ...
- 38.6k
2
votes
Accepted
Busy beaver sequence for a simple tag-like system
There is a recursive and even polynomial upper bound.
In the following I will denote the program string by $p$ and its length by $n$.
First notice that the memory will always be of the form $0^i$, $0^...
- 341
2
votes
Origin of tropical mathematics
The paper "Limited subsets of a free monoid" was published in 1978.
However, another paper
A. Mandel, I. Simon, On finite semigroups of matrices, Theoret. Comput. Sci. 5 (1977/78), no. 2, ...
- 841
2
votes
Accepted
Origin of tropical mathematics
This answer is due to Benjamin Steinberg:
Simon's paper is likely the first at least to make serious use of [the
tropical semiring] and it was in theoretical computer science to study
star height and ...
2
votes
A question on regular sets
An alternative answer to the second question, using very little information about regular languages, just that there are only countably many of them: Partition $\mathbb N-\{0,1\}$ into infinitely many ...
- 73.1k
2
votes
Accepted
A question on regular sets
The second question has a negative answer. The asymptotic behavior of $\pi_B(n)$ and $\pi_{B'}(n)$ would be the same, and if $\pi_B(n)$ satisfies any of the criteria for non-regularity on page 283 of ...
2
votes
Proof of dynamic programming calculation of Levenshtein distance
The easiest way to think about it is to view $\text{lev}(s1[0..i], s2[0..j])$ as the minimum cost of an alignment between $s1[0..i]$ and $s2[0..j]$.
For example $\texttt{AAACCCDDD}$ and $\texttt{...
- 981
1
vote
Origin of tropical mathematics
What is nowadays called "tropical semiring" was very explicitly defined and used by Bernard Carré in his 1971 paper An algebra for network routing problems. Its abstract:
Problems involving ...
- 17k
1
vote
Accepted
Shortest word accepted by a PDA
I think you can just solve the "obvious inequalities" to get a polynomial time algorithm. I.e. assume acceptance by empty stack, and for each pair of states $p$, $q$ and a stack symbol $t$, ...
- 6,652
1
vote
Can one reduce to 'reversing' the right multiplier finite-state automata of an automatic group to obtain a biautomatic structure?
I would like to give a couple of examples, which I hope illustrate my belief that you cannot derive a biautomatic structure for a group from an arbitrary automatic structure by some kind of general ...
- 37.4k
1
vote
decidability of regularity of a language depending on representation
Here is a simple example of a non decidable regular language. Take any language $L$ on the alphabet $A$. Then the shuffle product $A^* \mathrel{\raise 1mm{\llcorner\!\llcorner\!\!\!\lrcorner}} L$ (in ...
- 841
1
vote
Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?
Based on Gerhard Paseman's comment, I found the paper Correction, Optimization and Verification of Transition Rule Set for Waksman's Firing Squad Synchronization Algorithm by Umeo, Sogabe, and Nomura. ...
- 413
Only top scored, non community-wiki answers of a minimum length are eligible