# Questions tagged [universal-turing-machines]

The tag has no usage guidance.

16 questions
Filter by
Sorted by
Tagged with
33 views

### Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?

Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
49 views

### Asymptotic time required to simulate a Turing machine M for k steps

Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps. Wikipedia's page on EXPTIME-complete says it takes O(k) time ...
344 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 ...
224 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 ...
53 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 ...
121 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 ...
329 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 ...
931 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" ...
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 ...
426 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 ...
378 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 ...
71 views

682 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 ...