lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Mon, Apr 9, 2018 at 1:00 PM, Francisco Olarte <> wrote:
> On Mon, Apr 9, 2018 at 7:32 PM, Coda Highland <> wrote:
>> On Mon, Apr 9, 2018 at 12:19 PM, Francisco Olarte
>> <> wrote:
>>> On Mon, Apr 9, 2018 at 3:08 PM, Dirk Laurie <> wrote:
>>> ...
>>>> In fact, why have Lua at all since a Turing machine can do everything?
>>> Because you cannot implement a Turing Machine in a normal computer?
> ...
>> You can implement a sufficiently large finite approximation of a Turing Machine.
> You cannot do everything with that. I knew that, and I suspect the OP
> knows both my previous line and yours. I did not suspect you would
> fall for that.

Of course you can't do everything, but you can do everything you can
do with a finite computer with a finite Turing Machine. If an
algorithm can't be run on a finite Turing Machine, it can't be run on
a finite computer. But the Turing Machine would be ridiculously huge
and unusably slow (regardless of finite or infinite), which is why the
next part comes into the picture.

>> On the other hand, a Turing Machine (even a finite one) is a
>> ridiculously inefficient beast, and you can't implement a Turing
>> Machine optimizer in a Turing Machine. (You CAN implement one that
>> optimizes for the capabilities of a given hardware implementation, but
>> you by definition cannot make a Turing Machine whose purpose is to
>> make another Turing Machine that is capable of violating the rules of
>> a Turing Machine.) So where the rubber meets the road, you're gonna
>> need a programming language that isn't a Turing Machine. :P
> Which other hand? You cannot implement a turing machine in a normal
> computer, you cannot do everything ( meaning compute everything ) with
> a finite turing machine ( or with any finite machine, someone is going
> to find a problem which overflows, in fact I'm nearly sure that has
> already been done ).
> What I was trying to point is that we should not slide into that level
> of abstraction. Clearly not successful.

The other hand in this case is saying "just because you could build a
finite Turing Machine doesn't mean it's a good idea" -- in other
words, you WEREN'T unsuccessful; we agree.

> Also, you say "you cannot implement an optimizer" followed by "(You
> CAN implement one", contradiction? Did you forgot some qualifier? ( an
> optimizer does not need to violate any rule )....

I didn't forget the qualifier; it's there. The qualifier is "for the
capabilities of a given hardware implementation." Meaning, you can
build an optimizer that takes a Turing Machine and creates a
representation that can run efficiently given a specified physical

What you can't do is create an optimizer that will take a Turing
Machine and translate it into another Turing Machine that can run the
algorithm in fewer steps than an optimal equivalent Turing Machine can
run it in. That would be a contradiction. (Nothing prohibits you from
creating a Turing Machine optimizer that can identify suboptimal
machines and create a better, equivalent machine. However, that output
is still subject to the constraints of the Turing Machine formalism.)

/s/ Adam