Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [universal-turing-machines]

1
vote
2answers
133 views

For a specific unbounded Turing machine, is its Halting problem undecidable?

The question is on the title. To make it clearer, I state some facts. We all know that the Halting problem with input is undecidable. It leads to, given a specific input (e.g. empty string), the ...
1
vote
1answer
172 views

What is the VC dimension of Turing machines with specified maximum size?

Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine. I chose Turing machines in the question to make the question concrete, but I'm also more ...
-3
votes
1answer
48 views

About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$ [closed]

I'm studying Theory Of Computation and have some questions in the beginning: About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$ $HP =$ {$<M,w>$ $|$ $M$ is a $TM$ and it halts on ...
-2
votes
1answer
110 views

Can Pattern Recognition algorithms be considered Oracle Machines (in the Turing sense)?

I was reading Paul Churchland's "Engine of Reason, Seat of the Soul", where argues that humans (and potentially artificial neural networks as well) are capable of non-Turing computation because they ...
-1
votes
1answer
272 views

Where can I find a Turing machine evaluating arithmetic expressions? [closed]

Is there a Turing machine that can evaluate arithmetic operations with brackets containing +, -, and ...
1
vote
1answer
573 views

Multi Head universal Turing machine

It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" ...
-1
votes
3answers
389 views

Fastest Turing Machine

Recently I have been reading about Kolmogorov Complexity. As such I started thinking about the "fastest turing machine". In particular I am not interested in finding such a machine, I am only ...
2
votes
1answer
237 views

Is my language Turing-complete?

Consider a language like Brainfuck but without the brackets. At the end of each line (i.e. when "\n" occurs), if the current cell is not 0, then the line is re-executed. An example of an infinite ...
5
votes
0answers
63 views

How much smaller can universal Turing machines get if they only need to be universal for a subclass?

Say that a Turing machine $U$ is universal for a class $\mathcal{C}$ of languages if for any language $L \in \mathcal{C}$, there is a word $w_L$ with: $$(\forall w)\quad w \in L \Leftrightarrow U(w_L, ...
2
votes
1answer
122 views

Turing degree of Solomonoff semi-measure

We define the Solomonoff semi-measure $m$ on finite strings $x$ by $$m(x) = \sum_{p: U(p) = x} 2^{-l(p)},$$ where $U$ is a universal prefix Turing machine, $U(p) = x$ means $U$ outputs $x$ on input $...
28
votes
2answers
1k views

Can we not output the Kolmogorov complexity?

Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on ...
7
votes
1answer
543 views

Was bombe machine turing complete?

In the recent movie called The Imitation Game, there is a affirmation that Turing was building his theoretical machine. That machine is the Bombe Machine. Is this machine really equivalent to a Turing ...
9
votes
1answer
334 views

Is Kolmogorov complexity a surjective function?

Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,x) outputs whatever T outputs on input x (possibly both running forever). Define the Kolmogorov complexity ...
3
votes
1answer
220 views

What are different definitions of Universal Turing-machine?

I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines. Here are the ones I know, post below if you know ...