[FOM] universal machine as a primitive instruction

[Steve Stevenson]

I have my undergrad computability students, all computer science/math
majors, implement emulators (universal machines) for FSA, PDA, and Tm
(both deterministic and non-deterministic) in their favorite programming
language. Have your students do the same or get somebody to lay out the
programs (they're really quite straight forward). The students should then
be able to see the answer for themselves. You have to be able to read in
and search the instruction matrix, extend memory, and loop.

LBA might be able to do FSA if you fudge the register memory requirements
on the input. In general can't do PDA - restricted space for stack. It's
not immediately obvious LBA can't do LBA.

My $2 (inflation, you know)


On Fri, Apr 12, 2013 at 6:51 AM, <T.Forster at dpmms.cam.ac.uk> wrote:

> Have i missed answers to this? It seems like a sensible question if i
> understand it correctly. There obviously can be no universal FDA and (less
> obviously) no universal PDA. What about linear bounded automata? Is
> Turing-computable the only notion of computability that supports a
> universal machine?
>
>  If true, it looks like the kind of fact one would like to prove in a
> course like my fourth-year computability-and-logic course here...
>
>
>
> On Apr 10 2013, David Leduc wrote:
>
>  Hello,
>>
>> I have a question about computability. I am sure it is well known but
>> I cannot find the answer in my textbooks.
>>
>> For any system that is Turing complete, one can define a universal
>> machine in this system.
>>
>> But I want to do thing the other way round. Assume a system that has a
>> universal machine as one of its primitive instructions. What are the
>> other primitives needed to make this system Turing-complete?
>>
>> Thanks for any suggestion!!
>>
>> D.
>> ______________________________**_________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> http://www.cs.nyu.edu/mailman/**listinfo/fom<http://www.cs.nyu.edu/mailman/listinfo/fom>
>>
>>  ______________________________**_________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/**listinfo/fom<http://www.cs.nyu.edu/mailman/listinfo/fom>
>



-- 
D. E. (Steve) Stevenson
(Almost emeritus) Associate Professor
Clemson University
steve at clemson dot edu

"Those that know, do. Those that understand, teach," Aristotle.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130413/86e07ce5/attachment.html>