lua-users home
lua-l archive

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


On Mon, Apr 9, 2018 at 10:04 PM, Coda Highland <> wrote:
> On Mon, Apr 9, 2018 at 1:00 PM, Francisco Olarte <> wrote:
>> 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.

I know all of this. I think it should have been obvious from what I've
been writing. What I was trying to point is that if we start talking
about math things, like turing machines and the like, we should be
very precise in what we write, as minor omissions totally change the
subject in this kind of stuff.

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

Sory, english is not my first language and I must have written
something badly. I meant if you forgot to put a qualifier to the first
ocurrence of the optimizer word in the paragraph.

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

This sentence is some kind of logic trap ? A tatutology or something
like this, sorry but my logic vocabulary is decades rusty, and was not
learnt in English.

If you have an optimal you cannot have anything better, you can at
best equal it with another optimal, for any problem with any means. If
you manage to best it then you didn't had one to start with.

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

We all know this, but this proves what?

BTW, "the optimal equivalent..." was, IIRC, first mentioned in this message.

And what is this "Turing machine formalism", I've never heard of it.

Also, to discuss around a TM optimizer you have first to define an
scale of "goodness". What are you optimizing for, tape consumption for
a given problem, number of states in the machine, run time, a function
of these, other thing?

Francisco Olarte.