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

Why is the Turing machine considered effective computation if it's not realizable due to the 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.8k
22 votes

Why is the Turing machine considered effective computation if it's not realizable due to the 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
8 votes

Why is the Turing machine considered effective computation if it's not realizable due to the 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
7 votes
Accepted

Definition feels contradictory (Computational Complexity Theory)

$\mathbb{N}$ can be defined as the set of non-negative integers 0, 1, 2, ... You should check the definition in the book you're reading. However, there is no contradiction regardless of how $\mathbb{N}...
Pål GD's user avatar
  • 16.5k
5 votes

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

It's not clear your invocation of the 'Bekenstein bound' is sensible. This constrains the information in some volume, but why should your infinite tape need to be located in some small box near the ...
SethK's user avatar
  • 151
4 votes

Why is the Turing machine considered effective computation if it's not realizable due to the 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
4 votes

Why is the Turing machine considered effective computation if it's not realizable due to the 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
  • 41
2 votes

Why is the Turing machine considered effective computation if it's not realizable due to the 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 the Turing machine considered effective computation if it's not realizable due to the 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,694
2 votes

Polynomial solutions, one less

Suppose $L = \{(G_x, Y) \mid Y$ is the maximum or minimum vertex cover of $G_x\}$. This satisfies your requirements. Now let for $G_{x_0}$, we discard $Y_a$ as the maximum vertex cover (which is all ...
codeR's user avatar
  • 1,042
1 vote

Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?

Let's clarify the two models, looking at the definition of computability for a function $f : \mathbb{R} \to \mathbb{R}$ (because looking at individual real numbers is too simple a case to be ...
Arno's user avatar
  • 3,113
1 vote

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

I would like to present an answer that evokes the historical motivation for defining the Turing machine. You're solving mathematical problems. What kind of problems can you solve without any leap of ...
gnarrithas's user avatar
1 vote

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

Starting with the Bekenstein bound means you are already lost at the starting gate in terms of mathematics. Take. for example, addition. The existence of a number x + y is no longer true (no ...
Gree's user avatar
  • 11
1 vote

Why is the Turing machine considered effective computation if it's not realizable due to the 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

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