Skip to main content
Share Your Experience: Take the 2024 Developer Survey
22 votes

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

In addition to the fine answer by D.W. let me point out the difference between actual and potential infinity. A Turing machine is not actually infinite because at no point of its execution do we ...
Andrej Bauer's user avatar
  • 30.7k
14 votes

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

Turing machine are accepted because they are useful as a theoretical model. They are (relatively) easy to reason about, and the theory leads to insights that are useful. Please make sure to read ...
D.W.'s user avatar
  • 161k
2 votes

Can remainder mod 2 be efficiently computed from addition and equality?

I really like this question! Here's a sketchy argument for a negative answer (as expected) which I think works but may need some details filled in: Suppose our putative polytime parity-checking ...
Noah Schweber's user avatar
2 votes
Accepted

Computable function $F$ such that $F(e, x) = f(x), \forall x \in \mathbb N_0$

Yes there is. Such an $F$ is called a universal Turing machine. $e$ is then just an encoding of the Turing machine that computes $f$.
orlp's user avatar
  • 13.6k
2 votes

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

Suppose we do as you suggest, how would we decide how many states to use in our model? Is there something that makes an FSM with 1010 states fundamentally different from one with 1020 states? If you ...
Barmar's user avatar
  • 463
2 votes

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

The Turing machine is not necessary, either as an actual machine or an imaginary one, in order to prove the theorems that typically refer to it. It is only an easy-to-describe encapsulation of a ...
Twizzle's user avatar
  • 21
2 votes

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

This is like asking, "Why do we use real numbers like pi to model physical processes when human ability to measure is necessarily imprecise and finite?" First off, a Turing machine is not a ...
Trixie Wolf's user avatar
1 vote

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

Turing machines are accepted as the standard for effective computation because we don't think of computation as bounded by a fixed amount of resources. Take, for instance, adding two numbers. That's a ...
reinierpost's user avatar
  • 5,684
1 vote

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

I assume the OP is reacting to an assertion like this at the start of the Wikipedia article on the Bekenstein bound. That is, the primary criticism is about Turing machines being infinite: In ...
Daniel R. Collins's user avatar
1 vote

Why is turing machine considered effective computation if it's not realizable due to bekenstein bound?

I think we prefer TM as a model for its extended properties which not only allow us to answer quantitative questions about computing algorithms, but also more abstract questions which go beyond "...
Daniel S.'s user avatar
1 vote

Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

That is correct. A LBA uses bounded space and this can be used to simulate all possible computations (on a fixed input). It is not even necessary to keep track of loops in the simulation, just cutting ...
Hendrik Jan's user avatar
  • 30.8k
1 vote

Gödel's theorem and machines' power

I'm limited by Gödel's theorem, and I'm living quite happily with that. The same would be the case with a conscious or intelligent AI. If being limited by Gödel's theorem made you not intelligent, ...
gnasher729's user avatar
  • 30.4k
1 vote

Prove that a language does not many one reduce to its complement

You won't be able to prove this, because it is false. Let $J$ be an arbtirary undecidable language. Let $L = \{2n \mid n \in J\} \cup \{2n+1 \mid n \notin J\}$. Then $L$ is undecidable, and $L \...
Arno's user avatar
  • 3,103
1 vote
Accepted

What are the simplest examples of programs that we do not know whether they terminate?

Take any open problem in Number Theory and convert it into a question of whether a given program terminates. E.g. One example that works for the twin prime conjecture is: ...
HighAsAKiteOnMath's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible