Unanswered Questions
282 questions with no upvoted or accepted answers
14
votes
0
answers
270
views
What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?
In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
- 241
9
votes
1
answer
853
views
Turing Machine-Like Formalism for The Actor Model
Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.
The Actor Model is sometimes mentioned as a more powerful computational-...
CommunityBot
- 1
8
votes
0
answers
159
views
Make a tag system simulate a finite automaton?
Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
- 73.1k
6
votes
0
answers
543
views
What could we say about that conjecture that yields P != NP?
Let $F$ be the set of all Boolean formulae.
We say that a Boolean formula $\varphi$ is positive (=monotone) if
$\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
- 231
6
votes
0
answers
108
views
Calculating with regexes
We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
- 323
5
votes
0
answers
437
views
Where is simply typed lambda calculus on the Chomsky hiererchy?
The functions definable in untyped lambda calculus are the computable functions, for which it is in turn possible to define equivalences to the concepts of Turing machines, recursive enumerability and ...
- 815
5
votes
0
answers
55
views
The evolution of the term "recursive" from Goedel to Church to present day
I'm currently studying some of the history of computation / computability, in the early days known as recursion theory.
I see Goedel's definition of recursive functions seems significant in his paper,...
- 317
4
votes
0
answers
101
views
Necessity of encoding for certain models of computation
Consider the following model of computation (from here).
Although Fractran is Turing-complete, it assumes that the "user" is able to perform the steps of encoding the input ($2^{n + 1}$) ...
- 91
4
votes
0
answers
95
views
Is there a name for the class of functions whose totality can be proved using "Ackermann-like" reasoning?
Primitive recursion is recursion where totality can be proved because there is a single natural number parameter that strictly decreases in every recursive call. Put another way, the recursion ...
- 3,583
4
votes
0
answers
209
views
What is the computational class of a reduced Wang B-machine?
A Wang B-machine is Turing-complete and has only 4 instructions:
right: Move head right.
left: Move head left.
...
- 436
4
votes
0
answers
94
views
Direct reduction $L_{REG}\le_m L_{CFG}$
Both $L_{REG}=\{ \langle M \rangle : L(M)\text{ is regular}\}$ and $L_{CFG}=\{ \langle M \rangle : L(M)\text{ is context-free}\}$ are $\le_m$-complete for $\Sigma_3^0$ in the arithmetic hierarchy. ...
D.W.♦
- 167k
4
votes
0
answers
168
views
Undecidable problems with efficient heuristics
Are there some undecidable problems for which there are efficient heuristic algorithms, that succeed on a sufficiently large subset of inputs to be worth using?
The one application that comes to mind ...
- 539
4
votes
0
answers
96
views
Turing reductions by NX ∩ coNX and binary relation problems
Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
- 5,420
4
votes
0
answers
63
views
Polynomial Hierarchy and its Relation to Multi-Phase/States Physical Systems
We know that at the end computation should be done by physical systems which follow laws of physics. I know there are some researches that study the phase transition phenomenon in physics and try to ...
- 2,296
4
votes
1
answer
162
views
Proving a certain superset the halting language is not recursive
Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w ...
- 4,867