[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 247 KB, 736x732, 1342097909329.png [View same] [iqdb] [saucenao] [google]
5013939 No.5013939 [Reply] [Original]

So I get, if you wanna solve the Entscheidungsproblem, that you want to check if well-formed formulas get accepted by some univerals algorithm. Clearly a finite state machine is a thing, which does such a similar thing, and then also a turing machine does it.
But (maybe historically), what was the intention of creating something (the turing machine), which would write on the string you put in. In the end, this enables us to create wild programs, which do all kinds of things (compute stuff), and which don't just check if some string is accepted.
Was there a problem these were invented for or where they just a byproduct of the search for a better yes/no machine?

>> No.5014083
File: 67 KB, 500x360, high_school.jpg [View same] [iqdb] [saucenao] [google]
5014083

>> No.5014216
File: 28 KB, 576x524, for_reals.gif [View same] [iqdb] [saucenao] [google]
5014216

>> No.5014261

It's easy to show there are limits on what a finite state machine can recognize/accept because the machine is, well, finite. (For example, if you say that a theorem is "true" as long as all its parentheses balance, a FSM can't even recognize that.) A Turing machine is a simple extension of an FSM into an "infinite state machine". There are other extensions like push-down automata but Turing machines are the simplest that can basically compute anything that's a well-defined algorithm or function.

>> No.5016124

>>5014261
I don't know, do you feel that answered the question??

>> No.5016132

>>5014216
> discrete mathematics
> Studying real numbers

>> No.5016133

So if you're interested in this kind of thing you might want to check out the graphic novel "Logicomix" for a nice introduction. It covers all the history more or less before the advent of modern computer science.

There was a long-standing belief that if you could create a well-defined problem then we should be able to come up with an answer, that is to say ANY well-defined problem has a knowable answer. Obviously Godel proved this to be untrue, but that wouldn't happen for a while. So there was obviously intense interest in creating a universal problem solver so that we could plug in problems and output answers. Does that answer the question a little better?

>> No.5016139

Turing machines were always intended to be model computing machines.

>> No.5016157

Turing machines were proposed as being a machine that can compute anything that is computable in principle - and hence, any problem that CAN'T be solved by a Turing machine must be uncomputable. This way, through the undecidable halting problem, Turing machines were used in proving that the Entscheidungsproblem is impossible. That was their original purpose.

>> No.5016182

>>5016133
don't know, I thoght the plan was building a yes/no machine from the start

>> No.5016236

>>5016182
You can turn any statement, P, into the yes/no question - "is P true?". The concepts coincide.

>> No.5016257

>>5016236
well, "Was is 35^52?" is difficult to turn into a yes no statement. You'd have to make a million guesses. That's different from an algorithm, which actually computes the powers without answert what it might be

>> No.5016272

>>5016257
A yes/no machine could still calculate 35^52.
But Turing machines *are* more than yes/no machines, and that's an intentional feature of their design.
I'm not sure exactly what point you are trying to make.